Minimum Number of Flips to Make the Binary String Alternating

Hard
808.

Minimum Number of Flips to Make the Binary String Alternating

Minimum Number of Flips to Make the Binary String Alternating is a hard coding problem on strings, dynamic programming and greedy, asked in Amazon, Google and Nutanix interviews.

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'
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {string} s
 * @return {number}
 */
var minFlips = function(s) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Minimum Number of Flips to Make the Binary String Alternating Solution

Minimum Number of Flips to Make the Binary String Alternating solution: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.

Minimum Number of Flips to Make the Binary String Alternating is a hard coding problem on strings, dynamic programming and greedy, asked in Amazon, Google and Nutanix interviews.

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'

Hints for Minimum Number of Flips to Make the Binary String Alternating

  1. Hint 1

    A rotation of s is a window of length n inside s + s.

  2. Hint 2

    There are only two alternating targets of length n, so each window has two mismatch counts.

  3. Hint 3

    Roll both counts as the window slides, and the answer is the smallest of them all.

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

  1. Form t = s + s.
  2. 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.
  3. Once i >= n, remove index i - n from whichever counter it belonged to.
  4. 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

Java

public static int minFlips(String s) {
    int n = s.length();
    String t = s + s;
    int best = n, diff0 = 0, diff1 = 0;
    for (int i = 0; i < t.length(); i++) {
        char want0 = (i % 2 == 0) ? '0' : '1';
        if (t.charAt(i) != want0) diff0++; else diff1++;
        if (i >= n) {
            int j = i - n;
            char w0 = (j % 2 == 0) ? '0' : '1';
            if (t.charAt(j) != w0) diff0--; else diff1--;
        }
        if (i >= n - 1) {
            best = Math.min(best, Math.min(diff0, diff1));
        }
    }
    return best;
}

C++

int minFlips(string s) {
    int n = (int) s.size();
    string t = s + s;
    int best = n, diff0 = 0, diff1 = 0;
    for (int i = 0; i < (int) t.size(); i++) {
        char want0 = (i % 2 == 0) ? '0' : '1';
        if (t[i] != want0) diff0++; else diff1++;
        if (i >= n) {
            int j = i - n;
            char w0 = (j % 2 == 0) ? '0' : '1';
            if (t[j] != w0) diff0--; else diff1--;
        }
        if (i >= n - 1) {
            best = min(best, min(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#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 515 strings problems · the whole catalogue

Learn the technique: Strings · Dynamic Programming