Minimum Number of Flips to Make the Binary String Alternating

Step 1: Without rotation

There are only two alternating strings of length n: one starting with 0 ("0101...") and one starting with 1 ("1010..."). The flips needed are the mismatches with whichever of the two is closer.

Every character matches exactly one of the two patterns, so if diffA is the mismatch count with "0101...", the count with "1010..." is n - diffA.

Step 2: Rotations are windows of s + s

Type-1 operations are free, so we can try every rotation. Writing the string twice, t = s + s, every rotation of s appears in t as a window of length n.

For "111000", t is "111000111000", and its windows of length 6 are "111000", "110001", "100011", and so on.

Step 3: Slide the window and update the mismatch counts

Compare t against the long patterns "0101..." and "1010..." of length 2n. Each window of length n inside them is also alternating, so the mismatches inside the window are exactly the flips for that rotation.

• When character i enters, add it to diffA or diffB.
• When character i - n leaves, subtract it the same way.
• For every full window, the answer candidate is min(diffA, diffB).

s = "1110", so t = "11101110" and n = 4.

The patterns are lined up with positions in t, so a window that starts at an odd position is compared with them shifted by one. That swaps the two columns but does not change the minimum. Every rotation needs 1 flip, so the answer is 1.

The doubled string is built once; a character that is a mismatch for one pattern is a match for the other, so one comparison updates both counts.

public class MinimumNumberOfFlipsToMakeTheBinaryStringAlternate {

    public static int minFlips(String s) {
        int n = s.length();
        String t = s + s;                     // every rotation is a window of length n in t
        int diffA = 0;                        // mismatches with "0101..." in the window
        int diffB = 0;                        // mismatches with "1010..." in the window
        int best = Integer.MAX_VALUE;
        for (int i = 0; i < 2 * n; i++) {
            char expectA = (i % 2 == 0) ? '0' : '1';
            if (t.charAt(i) != expectA) {
                diffA++;
            } else {
                diffB++;                      // a match with one pattern is a miss for the other
            }
            if (i >= n) {                     // character i - n leaves the window
                char outExpectA = ((i - n) % 2 == 0) ? '0' : '1';
                if (t.charAt(i - n) != outExpectA) {
                    diffA--;
                } else {
                    diffB--;
                }
            }
            if (i >= n - 1) {
                best = Math.min(best, Math.min(diffA, diffB));
            }
        }
        return best;
    }

    public static void main(String[] args) {
        System.out.println(minFlips("111000"));   // 2
        System.out.println(minFlips("010"));      // 0
        System.out.println(minFlips("1110"));     // 1
    }
}

The original implementation, MinimumNumberOfFlipsToMakeTheBinaryStringAlternate.java, is on GitHub.

• Time: O(n): one pass over a string of length 2n.
• Space: O(n) for the doubled string. Indexing s with i % n avoids even that.

Doubling a string to see all its rotations also solves Rotate String.