Minimum Number of Flips to Make the Binary String Alternating — Hard Problem & Solution

Two operations are available on the binary string s: type 1: remove the first character and append it to the end (a rotation), usable any number of times;…

Difficulty: Hard
Topics: Strings, Dynamic Programming, Greedy, Sliding Window
Asked at: Amazon, Google, Nutanix
Time limit: 2 s
Memory limit: 256 MB
Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

Two operations are available on the binary string s:

type 1: remove the first character and append it to the end (a rotation), usable any number of times;
type 2: flip any single character.

Return the minimum number of type-2 operations needed to make s alternating (no two adjacent characters equal).

Example 1

Input: s = "111000"
Output: 2
Explanation: Rotate to "100011", then flip two characters to reach "101010".

Example 2

Input: s = "010"
Output: 0
Explanation: Already alternating.

Example 3

Input: s = "1110"
Output: 1

Constraints

1 <= s.length <= 100000
s[i] is '0' or '1'

How to solve Minimum Number of Flips to Make the Binary String Alternating

Rotations are free, so the real question is: over all rotations, what is the fewest flips to reach an alternating string? Every rotation appears as a length-n window of s + s, and each window's cost against the two alternating patterns rolls in constant time.

Approach

Form t = s + s.
Walk i over t, comparing t[i] with the pattern that has '0' at even absolute indices. Count mismatches in diff0; matches are mismatches for the other pattern, so they go to diff1.
Once i >= n, remove index i - n from whichever counter it belonged to.
From i = n - 1 onwards, the window is complete; take the minimum of diff0 and diff1.

Why it works

Using absolute index parity for the pattern means a window starting at an even index is compared with one alternating string and a window starting at an odd index with the other — but since the answer takes min(diff0, diff1) at every window, both patterns are covered regardless. The two counters always sum to the window length, which is why a match for one pattern is a mismatch for the other.

Complexity

Time — O(n)
Space — O(n)

Pitfalls

For odd n, rotations genuinely matter — the doubled string is what makes them all reachable; for even n the answer is the same as without rotations.
Starting to record the answer before i = n - 1 measures a partial window.
The two patterns are not interchangeable per window; both must be tracked.

Reference solution

Python

def minFlips(s: str) -> int:
    n = len(s)
    t = s + s
    best = n
    diff0 = diff1 = 0
    for i, ch in enumerate(t):
        want0 = "0" if i % 2 == 0 else "1"
        if ch != want0:
            diff0 += 1
        else:
            diff1 += 1
        if i >= n:
            j = i - n
            w0 = "0" if j % 2 == 0 else "1"
            if t[j] != w0:
                diff0 -= 1
            else:
                diff1 -= 1
        if i >= n - 1:
            best = min(best, diff0, diff1)
    return best

JavaScript

var minFlips = function(s) {
    var n = s.length;
    var t = s + s;
    var best = n, diff0 = 0, diff1 = 0;
    for (var i = 0; i < t.length; i++) {
        var want0 = i % 2 === 0 ? "0" : "1";
        if (t.charAt(i) !== want0) diff0++; else diff1++;
        if (i >= n) {
            var j = i - n;
            var w0 = j % 2 === 0 ? "0" : "1";
            if (t.charAt(j) !== w0) diff0--; else diff1--;
        }
        if (i >= n - 1) {
            if (diff0 < best) best = diff0;
            if (diff1 < best) best = diff1;
        }
    }
    return best;
};

Also on the editorial tab: C, C#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 282 strings problems · the whole catalogue