Minimum Changes To Make Alternating Binary String - Solution & Explanation

Problem Overview: You are given a binary string s. The goal is to determine the minimum number of character flips required to transform it into an alternating string. An alternating binary string has no two adjacent characters equal, meaning it must follow either the pattern 010101... or 101010....

The key observation: only two valid alternating patterns exist for any length. If you compare the input string against both patterns and count mismatches, the smaller mismatch count gives the minimum number of flips needed.

Approach 1: Compare to Two Patterns (O(n) time, O(1) space)

Iterate through the string once while comparing each character with the expected character for two possible patterns: one starting with '0' (0101...) and one starting with '1' (1010...). For index i, the expected character depends on parity: even indices match the starting bit, odd indices match the opposite bit. Maintain two counters for mismatches—one for each pattern. Each time s[i] differs from the expected character, increment the corresponding counter. After scanning the entire string, return the smaller mismatch count.

This approach uses a simple string traversal with constant bookkeeping. No additional data structures are required. The algorithm runs in O(n) time because each character is processed exactly once, and it uses O(1) space since only two counters are maintained. This is the most common solution in interviews and production code because it is both minimal and easy to reason about.

Approach 2: Precomputed Masks (O(n) time, O(n) space)

Another way to solve the problem is to explicitly build the two target alternating strings of the same length as s. Construct one mask mask1 = "0101..." and another mask2 = "1010...". Then iterate through the original string and count the number of positions where s[i] differs from each mask. The minimum mismatch count between the two masks represents the number of flips needed.

This approach still performs a single pass over the string, giving O(n) time complexity. However, it allocates additional memory for the two mask strings, resulting in O(n) space complexity. The logic is straightforward and sometimes easier for beginners because the expected pattern is explicitly represented rather than computed dynamically.

Recommended for interviews: The two-pattern comparison approach is the expected solution. It demonstrates strong reasoning about string patterns and avoids unnecessary memory allocation. The mask approach shows correct thinking but adds extra space without improving runtime. Interviewers typically look for the constant-space scan because it proves you recognized that only two alternating patterns are possible.