Min Flips for Alternate
JavaView on GFG
Problem Overview
A binary string is alternating when it matches either 0101...
Intuition
A binary string is alternating when it matches either 0101... or 1010.... Those two targets are bitwise complements of each other at every index, so a character that mismatches the first pattern automatically matches the second. Counting mismatches against 0101... is therefore enough: the flip cost for 1010... is n minus that count, and the answer is the smaller of the two.
Algorithm
- 1Walk the string once and count positions where the character differs from 0 on even indices and 1 on odd indices.
- 2Let that count be mismatch.
- 3Return the minimum of mismatch and n minus mismatch.
Example Walkthrough
Input: s = "001"
- 1. The target 010 differs from the string only at index 1, so one flip is enough for that pattern.
- 2. The target 101 differs at two positions, which equals length minus one.
- 3. The cheaper option needs one flip, so the answer is 1.
Output: 1
Common Pitfalls
- • Only two alternating targets exist for a binary alphabet. Do not search over other patterns.
- • The complement shortcut assumes every character is 0 or 1. Mixed alphabets would need both counters.
- • Index parity starts at 0. Flipping which pattern you count against still yields the same minimum.
- • A full second pass is unnecessary once you store n minus the first mismatch count.
Min Flips for Alternate.java
Java
// Approach: An alternating string is either 0101... or 1010.... Count mismatches
// against 0101.... The other pattern mismatches on every other position, so its
// flip count is n minus that value. Return the smaller of the two.
// Complexity: O(n) time, O(1) extra space.
class Solution {
public int minFlips(String s) {
int n = s.length();
int mismatch = 0;
for (int i = 0; i < n; i++) {
char expect = (i % 2 == 0) ? '0' : '1';
if (s.charAt(i) != expect)
mismatch++;
}
return Math.min(mismatch, n - mismatch);
}
}Was this solution helpful?