Number of flips to make binary string alternate

The problem, simply

You get a string of 0 and 1. One flip turns a single 0 into 1 or a 1 into 0. Find the fewest flips so that no two neighbors are the same.

There are only two strings like that for any length: one that starts with 0 (0101...) and one that starts with 1 (1010...). The answer is the cheaper of the two.

A story to remember it

Picture it

Examples

Way 1: the simple way

Write out both goal strings in full. Then compare s with each one, letter by letter, and count how many places differ.

1. Build goal A: 0 at even places, 1 at odd places.
2. Build goal B: the opposite.
3. Count where s differs from each goal. Return the smaller count.

class Solution {
    public int minFlips(String s) {
        int n = s.length();
        StringBuilder a = new StringBuilder(), b = new StringBuilder();
        for (int i = 0; i < n; i++) {
            a.append(i % 2 == 0 ? '0' : '1');     // 0101...
            b.append(i % 2 == 0 ? '1' : '0');     // 1010...
        }
        int flipsA = 0, flipsB = 0;
        for (int i = 0; i < n; i++) {
            if (s.charAt(i) != a.charAt(i)) flipsA++;
            if (s.charAt(i) != b.charAt(i)) flipsB++;
        }
        return Math.min(flipsA, flipsB);
    }
}

How long it takes: a few walks over the string, O(n). Extra room: two goal strings as long as s, O(n).

Way 2: the clever way

You do not need to write the goals down. Goal A wants i % 2 at place i: 0 at even places and 1 at odd places. And every place that agrees with goal A disagrees with goal B. So count only the flips for A, and B costs n - flipsA.

1. For each place i, the digit is s[i] - '0' and goal A wants i % 2.
2. If they differ, add one to flipsA.
3. Return min(flipsA, n - flipsA).

class Solution {
    public int minFlips(String s) {
        int n = s.length();
        int flipsA = 0;                              // flips to reach 0101...
        for (int i = 0; i < n; i++) {
            int digit = s.charAt(i) - '0';
            if (digit != i % 2) flipsA++;            // goal A wants i % 2 here
        }
        return Math.min(flipsA, n - flipsA);         // goal B is the opposite
    }
}

How long it takes: one walk, O(n). Extra room: one counter, O(1).

Watch out for

• Compare the digit with the number i % 2, not the character. '0' is 48, not 0, so convert with - '0'.
• The empty string and a single digit need 0 flips. The formula gives 0 for both.
• If the string can hold other characters, check them first.

What interviewers ask next

• Swaps instead of flips (LeetCode 1864)? Swaps cannot change how many 0s and 1s there are. Pick a goal whose counts match, then the answer is half the number of places that disagree with it.
• You may also move the first digit to the end, any number of times (LeetCode 1888)? Glue s + s and slide a window of length n, keeping the mismatch count for both goals as the window moves. Still O(n).
• Return the fixed string, not just the count? Build the cheaper goal.
• Same idea on a grid, like a chessboard? A cell (r, c) wants (r + c) % 2. Count mismatches and take the smaller of the count and its opposite.

Remember this

Grown-up words: the tiles are bits, repainting is a bit flip, the two floors are the two alternating target patterns, and n - flipsA uses the fact that the patterns are complements of each other.