Minimum Changes To Make Alternating Binary String

How it works

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.

Steps

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.

Complexity

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

Things to watch for

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.

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)

class Solution {
public:
    int minOperations(string s) {
        int count = 0;

        for (int i = 0; i < s.size(); i++) {
            if (i % 2 == 0) {
                if (s[i] == '0') {
                    count++;
                }
            } else {
                if (s[i] == '1') {
                    count++;
                }
            }
        }

        return min(count, (int)s.size() - count);
    }
};