Minimum Number of Flips to Make the Binary String Alternating

How it works

First, count mismatches for the original string against pattern "1010...". The mismatch count for "0101..." is simply n - start_1 since every position either matches one pattern or the other.

For odd-length strings, rotating changes parity. After one rotation, positions that needed a '0' now need a '1' and vice versa. We can compute the new mismatch counts by swapping and adjusting based on the character that moved from front to back.

Steps

1. Count initial mismatches (start_1) against pattern "101...".
2. Compute start_0 = n - start_1 for pattern "010...".
3. If n is even, rotations do not change the answer, so return min(start_0, start_1).
4. For odd n, simulate each rotation:
   • Swap dp0 and dp1 (parity flip).
   • Adjust counts based on the character that rotated.
   • Track minimum across all rotations.

Complexity

• Time complexity: O(n)
• Space complexity: O(1) extra space.

Things to watch for

Forgetting That Rotations Only Matter for Odd-Length Strings

For even-length strings, rotating the string does not change the number of flips needed because the parity of each position remains the same after a full rotation cycle. The optimization to skip rotations when n % 2 == 0 is critical for both correctness and performance. Without this check, you might perform unnecessary work or miss that the initial comparison already gives the optimal answer.

Incorrectly Handling the Doubled String in Sliding Window

When using the sliding window approach with s + s, you must build alternating patterns of length 2n, not n. If you only build patterns of length n and try to index beyond, you will get index-out-of-bounds errors or incorrect mismatch counts. Additionally, when the window slides, you must properly remove the contribution of the leftmost character before adding the new rightmost character.

Confusing Which Pattern Tracks Which Mismatches

The two patterns "010101..." and "101010..." are complementary. If a position matches one pattern, it mismatches the other. When computing both diff counts simultaneously, ensure you are consistent: if s[r] != alt1[r], increment diff1; if s[r] != alt2[r], increment diff2. Mixing up which count corresponds to which pattern will produce incorrect minimum flip counts.

class Solution:
    def minFlips(self, s: str) -> int:
        start_1 = 0
        for i in range(len(s)):
            if i & 1:
                start_1 += s[i] == "1"
            else:
                start_1 += s[i] == "0"

        start_0 = len(s) - start_1
        ans = min(start_0, start_1)
        if len(s) % 2 == 0:
            return ans

        dp0, dp1 = start_0, start_1
        for c in s:
            dp0, dp1 = dp1, dp0
            if c == "1":
                dp0 += 1
                dp1 -= 1
            else:
                dp0 -= 1
                dp1 += 1
            ans = min(dp0, dp1, ans)
        return ans

class Solution {
public:
    int minFlips(string s) {
        int start_1 = 0, n = s.size();

        for (int i = 0; i < n; i++) {
            if (i & 1) {
                start_1 += (s[i] == '1');
            } else {
                start_1 += (s[i] == '0');
            }
        }

        int start_0 = n - start_1;
        int ans = min(start_0, start_1);
        if (n % 2 == 0) {
            return ans;
        }

        int dp0 = start_0, dp1 = start_1;
        for (char c : s) {
            int temp = dp0;
            dp0 = dp1;
            dp1 = temp;
            if (c == '1') {
                dp0++;
                dp1--;
            } else {
                dp0--;
                dp1++;
            }
            ans = min({ans, dp0, dp1});
        }

        return ans;
    }
};