DDSA Solutions

Min Flips for Alternate

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

  1. 1Walk the string once and count positions where the character differs from 0 on even indices and 1 on odd indices.
  2. 2Let that count be mismatch.
  3. 3Return the minimum of mismatch and n minus mismatch.

Example Walkthrough

Input: s = "001"

  1. 1. The target 010 differs from the string only at index 1, so one flip is enough for that pattern.
  2. 2. The target 101 differs at two positions, which equals length minus one.
  3. 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?