Minimum Changes To Make Alternating Binary String: Greedy Counting Pattern

LeetCode 1758, Minimum Changes To Make Alternating Binary String, gives you a binary string s consisting only of '0' and '1'. You need to return the minimum number of changes required to make the string alternating. A string is alternating if no two adjacent characters are the same.

For example:

• "0100" returns 1 (change the last character to '1' to get "0101")
• "10" returns 0 (already alternating)
• "1111" returns 2 (change to "1010" or "0101", both need 2 flips)

Why this problem matters

This problem teaches a fundamental greedy insight: when the number of valid target states is small, you can simply compare against all of them and pick the best. Many string and array problems share this structure. Instead of searching through a large space of possibilities, you recognize that the answer must look like one of a handful of templates.

The key insight

There are only two possible alternating binary strings of any given length. One starts with '0' ("0101...") and the other starts with '1' ("1010..."). Every alternating string must be one of these two patterns.

This means you do not need to figure out which characters to flip or in what order. You just count how many positions in the input differ from each pattern. The minimum of those two counts is your answer.

There is also a nice shortcut: if count0 is the number of mismatches against the pattern starting with '0', then the mismatches against the other pattern is n - count0. Every position that matches one pattern must mismatch the other, and vice versa.

The solution

def min_operations(s: str) -> int:
    count = 0
    for i in range(len(s)):
        if s[i] != str(i % 2):
            count += 1
    return min(count, len(s) - count)

Here is what happens step by step:

1. Walk through the string one character at a time.
2. At each index i, the expected character for the "0101..." pattern is str(i % 2). If the actual character differs, increment count.
3. After the loop, count holds the mismatches against "0101...". The mismatches against "1010..." is len(s) - count.
4. Return whichever is smaller.

Visual walkthrough

Here is the algorithm running on the string "0100", comparing against both alternating patterns.

Pattern "0101" has 1 mismatch (at index 3). Pattern "1010" has 3 mismatches (at indices 0, 1, and 2). The answer is min(1, 3) = 1.

Complexity analysis

You scan the string once, doing a constant amount of work per character. No extra data structures are needed, just a single counter. This is optimal because you must read every character at least once to know whether it needs to change.

The building blocks

1. Modular index parity

The pattern of using i % 2 to determine an expected value at each position shows up whenever you need to check or generate alternating sequences. The idea is that even indices get one value and odd indices get the other. You will see this same technique in problems involving checkerboard patterns, alternating colors, and zigzag arrangements.

expected = i % 2

This single expression tells you exactly what character belongs at position i in the "0101..." pattern. For the other pattern, the expected value is 1 - i % 2.

2. Complement counting

When a string must match one of exactly two complementary patterns, you only need to count mismatches for one of them. The mismatch count for the other pattern is n - count. This works because every position either matches pattern A or pattern B, never both and never neither.

other_count = len(s) - count

This eliminates a second pass through the string and cuts your work in half. The same complement trick applies in any scenario where you partition elements into two mutually exclusive groups.

Edge cases

Already alternating. The string "010101" has zero mismatches against the first pattern. The function returns min(0, 6) = 0. No changes needed.

Single character. The string "0" or "1" is already alternating by definition. The function returns 0.

All same characters. The string "0000" has 2 mismatches against "0101" and 2 mismatches against "1010". The answer is 2. For odd-length strings like "000", one pattern needs 1 change and the other needs 2.

Length 2. The string "00" needs 1 change (to "01" or "10"). The string "01" or "10" needs 0 changes.

From understanding to recall

You can read through this solution and feel like you fully get it. The logic is clean, the code is short. But will you remember the complement counting trick two weeks from now when you encounter a similar problem? Will the i % 2 parity check come to you automatically?

Spaced repetition locks in these building blocks. Instead of re-reading the full solution before every interview, you drill the individual pieces (modular index parity, complement counting, greedy template comparison) at increasing intervals. After a few reps spread across days, the pattern is stored in long-term memory. When you sit down for a coding screen and see a string problem with a small number of valid targets, the approach is already there.

Related posts

• Valid Palindrome - Another string comparison pattern
• Longest Substring Without Repeating Characters - String traversal patterns
• Reverse String - Foundational string manipulation

CodeBricks breaks problems like this into their smallest reusable building blocks and drills them with spaced repetition. You stop memorizing solutions and start building fluency with the techniques that transfer across hundreds of problems.