LeetCode 1758 - Minimum Changes To Make Alternating Binary String

The problem gives us a binary string s, which means the string contains only the characters '0' and '1'. In one operation, we are allowed to flip a character, meaning we can change '0' into '1' or '1' into '0'.

leetcodeeasystring

LeetCode Problem 1758

Difficulty: 🟢 Easy
Topics: String

Solution

Problem Understanding

The problem gives us a binary string s, which means the string contains only the characters '0' and '1'. In one operation, we are allowed to flip a character, meaning we can change '0' into '1' or '1' into '0'.

Our goal is to transform the string into an alternating binary string using the minimum number of operations.

An alternating binary string is a string where no two adjacent characters are equal. Since the string only contains two possible characters, there are only two valid alternating patterns possible for any given length:

  • A string starting with '0', such as "010101..."
  • A string starting with '1', such as "101010..."

The task is therefore equivalent to determining how many characters must be changed to match each of these two possible patterns, then returning the smaller value.

The input size constraint is:

  • 1 <= s.length <= 10^4

This tells us the string is relatively small, but we should still aim for a linear time solution. A quadratic approach would still technically pass for this constraint, but it would be unnecessarily inefficient for such a straightforward problem.

Several edge cases are important to consider:

  • A string of length 1 is already alternating, regardless of whether it is "0" or "1".
  • A string that is already alternating should return 0.
  • A string where all characters are the same, such as "1111", requires multiple flips.
  • Odd and even length strings behave slightly differently in terms of pattern endings, but the alternating pattern logic remains the same.

The problem guarantees that every character is either '0' or '1', so we do not need to validate input characters.

Approaches

Brute Force Approach

A brute force solution would explicitly generate both possible alternating strings of the same length as s.

For example, if s = "0100":

  • Pattern 1 would be "0101"
  • Pattern 2 would be "1010"

We would then compare the original string against both patterns character by character and count how many positions differ. Each differing position represents one required operation.

Finally, we would return the smaller mismatch count.

This approach is correct because any valid alternating binary string must follow one of the two alternating patterns. Since we check both possibilities completely, we are guaranteed to find the minimum number of changes.

Although this solution is already efficient enough for the given constraints, it uses additional space to construct the pattern strings.

Optimal Approach

The key observation is that we do not actually need to build the alternating strings.

Instead, we can determine what character should appear at each position based on the index parity:

  • For the pattern starting with '0':

  • Even indices should contain '0'

  • Odd indices should contain '1'

  • For the pattern starting with '1':

  • Even indices should contain '1'

  • Odd indices should contain '0'

As we iterate through the string once, we count mismatches for both patterns simultaneously.

If the current character does not match the expected character for a pattern, that pattern requires one change at this position.

At the end, we return the smaller mismatch count.

This eliminates unnecessary string construction while keeping the algorithm simple and efficient.

Approach Time Complexity Space Complexity Notes
Brute Force O(n) O(n) Builds both alternating patterns explicitly
Optimal O(n) O(1) Counts mismatches directly without extra strings

Algorithm Walkthrough

  1. Initialize two counters:
  • start_with_zero
  • start_with_one

These counters represent how many changes are needed if the alternating string begins with '0' or '1'. 2. Iterate through the string using the index i. 3. For each position, determine the expected character for both patterns.

If the pattern starts with '0':

  • Even index → expected '0'
  • Odd index → expected '1'

If the pattern starts with '1':

  • Even index → expected '1'
  • Odd index → expected '0'
  1. Compare the current character against both expected values.

If the character does not match the expected value for a pattern, increment that pattern's mismatch counter. 5. Continue until all characters have been processed. 6. Return the smaller of the two counters because that represents the minimum number of operations required.

Why it works

Every alternating binary string must follow exactly one of two possible structures: starting with '0' or starting with '1'. The algorithm independently counts how many characters must change to match each structure. Since every mismatch corresponds to exactly one required operation, the smaller mismatch count is the optimal answer.

Python Solution

class Solution:
    def minOperations(self, s: str) -> int:
        start_with_zero = 0
        start_with_one = 0

        for index, char in enumerate(s):
            expected_zero_pattern = '0' if index % 2 == 0 else '1'
            expected_one_pattern = '1' if index % 2 == 0 else '0'

            if char != expected_zero_pattern:
                start_with_zero += 1

            if char != expected_one_pattern:
                start_with_one += 1

        return min(start_with_zero, start_with_one)

The implementation follows the algorithm directly.

Two counters are maintained throughout the traversal. For each character, the code computes what value should appear at the current index for both alternating patterns.

The expression index % 2 == 0 determines whether the current position is even or odd. Based on this parity, the expected character is selected.

Whenever the current character differs from the expected one, the corresponding mismatch counter increases by one.

After processing the entire string, the minimum of the two counters is returned because it represents the fewest changes needed to make the string alternating.

Go Solution

func minOperations(s string) int {
    startWithZero := 0
    startWithOne := 0

    for i := 0; i < len(s); i++ {
        var expectedZeroPattern byte
        var expectedOnePattern byte

        if i%2 == 0 {
            expectedZeroPattern = '0'
            expectedOnePattern = '1'
        } else {
            expectedZeroPattern = '1'
            expectedOnePattern = '0'
        }

        if s[i] != expectedZeroPattern {
            startWithZero++
        }

        if s[i] != expectedOnePattern {
            startWithOne++
        }
    }

    if startWithZero < startWithOne {
        return startWithZero
    }

    return startWithOne
}

The Go implementation mirrors the Python logic closely.

Since Go strings are indexed as bytes, the solution uses byte variables for expected characters. The algorithm still performs a single pass through the string and maintains two mismatch counters.

There are no concerns about integer overflow because the maximum string length is only 10^4.

Worked Examples

Example 1

Input:

s = "0100"

We compare the string against both alternating patterns.

Index Character Expected for "0101" Mismatch Count Expected for "1010" Mismatch Count
0 0 0 0 1 1
1 1 1 0 0 2
2 0 0 0 1 3
3 0 1 1 0 3

Final counts:

  • Start with '0' → 1
  • Start with '1' → 3

Answer:

1

Example 2

Input:

s = "10"
Index Character Expected for "01" Mismatch Count Expected for "10" Mismatch Count
0 1 0 1 1 0
1 0 1 2 0 0

Final counts:

  • Start with '0' → 2
  • Start with '1' → 0

Answer:

0

Example 3

Input:

s = "1111"
Index Character Expected for "0101" Mismatch Count Expected for "1010" Mismatch Count
0 1 0 1 1 0
1 1 1 1 0 1
2 1 0 2 1 1
3 1 1 2 0 2

Final counts:

  • Start with '0' → 2
  • Start with '1' → 2

Answer:

2

Complexity Analysis

Measure Complexity Explanation
Time O(n) The algorithm processes each character exactly once
Space O(1) Only a few integer counters are used

The solution performs a single linear scan of the input string. No nested loops or additional data structures proportional to input size are used. Therefore, the runtime grows linearly with the length of the string, while memory usage remains constant.

Test Cases

solution = Solution()

assert solution.minOperations("0100") == 1  # One flip needed at the last position
assert solution.minOperations("10") == 0  # Already alternating
assert solution.minOperations("1111") == 2  # Half the characters must change
assert solution.minOperations("0") == 0  # Single character is already alternating
assert solution.minOperations("1") == 0  # Single character is already alternating
assert solution.minOperations("00") == 1  # One character must flip
assert solution.minOperations("01") == 0  # Already alternating
assert solution.minOperations("101010") == 0  # Perfect alternating pattern
assert solution.minOperations("10010100") == 3  # Mixed mismatches
assert solution.minOperations("000000") == 3  # Every other character must change
assert solution.minOperations("10101") == 0  # Odd length alternating string
assert solution.minOperations("1101001") == 2  # Random binary string
Test Why
"0100" Verifies standard single-change scenario
"10" Confirms already alternating input
"1111" Tests repeated identical characters
"0" Minimum input size
"1" Minimum input size with different value
"00" Small even-length non-alternating case
"01" Small alternating case
"101010" Larger already-valid alternating pattern
"10010100" Mixed mismatch positions
"000000" Worst-case repeated zeros
"10101" Odd-length alternating pattern
"1101001" General random test case

Edge Cases

Single Character Strings

A string with only one character is always alternating because there are no adjacent characters to compare. A buggy implementation might incorrectly attempt to compare neighbors or assume at least two characters exist. This solution handles the case naturally because the mismatch counters remain zero for one of the two valid patterns.

Strings With All Identical Characters

Inputs such as "0000" or "111111" are important because they require flipping every other character. A naive implementation might incorrectly try to greedily fix adjacent duplicates without considering the global alternating structure. This algorithm avoids that issue by comparing against both complete alternating patterns.

Already Alternating Strings

Inputs like "010101" or "1010" should return 0. Some incorrect solutions accidentally perform unnecessary operations because they only test one starting pattern. This implementation evaluates both valid alternating configurations and correctly identifies when no changes are needed.