Number of flips to make binary string alternate

Problem Statement

Given a binary string, find the minimum number of characters to flip to make the string alternating. An alternating string has no two adjacent characters that are the same (either "010101..." or "101010...").

Example:

• Input: "001"
• Output: 1
• Explanation: Flip the first character to get "101" (alternating)

Example 2:

• Input: "0001010111"
• Output: 2
• Explanation: Flip positions to make it alternate

Approach 1: Generate Both Patterns (Brute Force)

Intuition

There are only two possible alternating patterns: starting with '0' (010101...) or starting with '1' (101010...). Generate both patterns and count mismatches for each.

Algorithm

1. Generate pattern starting with '0' of length n
2. Generate pattern starting with '1' of length n
3. Count mismatches between input and each pattern
4. Return minimum of the two counts

public class Solution {
    public int minFlips(String s) {
        int n = s.length();
        
        // Generate pattern starting with '0': "010101..."
        StringBuilder sb0 = new StringBuilder();
        for (int i = 0; i < n; i++) {
            sb0.append(i % 2 == 0 ? '0' : '1');
        }
        String pattern0 = sb0.toString();
        
        // Generate pattern starting with '1': "101010..."
        StringBuilder sb1 = new StringBuilder();
        for (int i = 0; i < n; i++) {
            sb1.append(i % 2 == 0 ? '1' : '0');
        }
        String pattern1 = sb1.toString();
        
        // Count mismatches
        int flips0 = 0, flips1 = 0;
        for (int i = 0; i < n; i++) {
            if (s.charAt(i) != pattern0.charAt(i)) flips0++;
            if (s.charAt(i) != pattern1.charAt(i)) flips1++;
        }
        
        return Math.min(flips0, flips1);
    }
}

Complexity Analysis

• Time Complexity: O(n) - Single pass after generating patterns
• Space Complexity: O(n) - Storing the two patterns

Approach 2: Count Without Generating Patterns (Optimal)

Intuition

We don't need to actually generate the patterns. At each position:

• For pattern starting with '0': expected char is '0' at even indices, '1' at odd indices
• For pattern starting with '1': expected char is '1' at even indices, '0' at odd indices

Just count mismatches on the fly.

Algorithm

1. Initialize two counters for flips needed for each pattern
2. Iterate through the string
3. At each position, determine expected character for both patterns
4. Increment counter if character doesn't match expected
5. Return minimum

public class Solution {
    public int minFlips(String s) {
        int n = s.length();
        int flips0 = 0;  // Flips for pattern "010101..."
        int flips1 = 0;  // Flips for pattern "101010..."
        
        for (int i = 0; i < n; i++) {
            // For pattern starting with '0'
            char expected0 = (i % 2 == 0) ? '0' : '1';
            
            if (s.charAt(i) != expected0) {
                flips0++;
            } else {
                flips1++;  // If matches pattern0, doesn't match pattern1
            }
        }
        
        return Math.min(flips0, flips1);
    }
}

Complexity Analysis

• Time Complexity: O(n) - Single pass
• Space Complexity: O(1) - Only using two counters

Approach 3: Using Bit Manipulation

Intuition

Convert character comparison to integer comparison. At position i:

• Expected for pattern0: i % 2
• Actual: s[i] - '0'
• They differ if (i % 2) != (s[i] - '0') which is same as (i % 2) ^ (s[i] - '0')

public class Solution {
    public int minFlips(String s) {
        int n = s.length();
        int flips0 = 0;
        
        for (int i = 0; i < n; i++) {
            // XOR: 1 if they differ, 0 if same
            flips0 += (i & 1) ^ (s.charAt(i) - '0');
        }
        
        // Flips for pattern1 = n - flips0
        return Math.min(flips0, n - flips0);
    }
}

Dry Run Example

Complexity Analysis

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

Variation: Circular String

If the string is circular (last character adjacent to first), the problem becomes more complex.

Key Takeaways

1. Only two possible target patterns - This simplifies the problem significantly
2. Pattern relationship: flips1 = n - flips0 because patterns are complements
3. Bit manipulation provides elegant solution with XOR
4. No extra space needed once we realize we can compute on the fly
5. For circular variants, use sliding window on doubled string
6. This is a common interview problem testing pattern recognition