1758. Minimum Changes To Make Alternating Binary String - Explanation

Problem Link



1. Start with Zero and One

Intuition

An alternating binary string must follow one of two patterns: starting with '0' (like "010101...") or starting with '1' (like "101010..."). We simply count how many characters differ from each pattern and return the smaller count.

We use XOR to toggle the expected character at each position. Starting with 0, we XOR with 1 after each character to alternate between expecting 0 and 1.

Algorithm

  1. Initialize cnt1 = 0 and expected character cur = 0 (pattern starting with '0').
  2. For each character in the string:
    • If the character does not match cur, increment cnt1.
    • Toggle cur using XOR with 1.
  3. Repeat with cur = 1 (pattern starting with '1') to get cnt2.
  4. Return the min of cnt1 and cnt2.
class Solution:
    def minOperations(self, s: str) -> int:
        cur = cnt1 = 0
        for c in s:
            if int(c) != cur:
                cnt1 += 1
            cur ^= 1

        cur = 1
        cnt2 = 0
        for c in s:
            if int(c) != cur:
                cnt2 += 1
            cur ^= 1

        return min(cnt1, cnt2)

Time & Space Complexity

  • Time complexity: O(n)O(n)
  • Space complexity: O(1)O(1)

2. Start with Zero or One

Intuition

We can optimize by counting mismatches for only one pattern. Notice that if a position mismatches the "start with 1" pattern, it must match the "start with 0" pattern, and vice versa. So the count for one pattern plus the count for the other equals the string length.

We count mismatches for the "start with 1" pattern (where even indices should be '1' and odd indices should be '0'). The count for the "start with 0" pattern is simply length - count.

Algorithm

  1. Initialize count = 0.
  2. For each index i:
    • If i is even and s[i] == '0', increment count.
    • If i is odd and s[i] == '1', increment count.
  3. Return the min of count and length - count.
class Solution:
    def minOperations(self, s: str) -> int:
        count = 0

        for i in range(len(s)):
            if i % 2 == 0:
                count += 1 if s[i] == '0' else 0
            else:
                count += 1 if s[i] == '1' else 0

        return min(count, len(s) - count)

Time & Space Complexity

  • Time complexity: O(n)O(n)
  • Space complexity: O(1)O(1)

Common Pitfalls

Only Checking One Pattern

An alternating binary string can start with either '0' (giving "010101...") or '1' (giving "101010..."). A common mistake is only counting mismatches against one pattern and returning that count. You must compare against both patterns and return the minimum of the two counts, or use the relationship that the two counts sum to the string length.

Incorrect Character-to-Integer Conversion

When comparing characters to expected values (0 or 1), ensure proper conversion. In many languages, '0' and '1' are characters with ASCII values 48 and 49, not the integers 0 and 1. Use c - '0' or parseInt(c) to convert correctly. Directly comparing the character '0' to the integer 0 will give wrong results in most languages.