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.
- 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 <= 100000s[i] is '0' or '1'
Hints for Minimum Number of Flips to Make the Binary String Alternating
Hint 1
A rotation of
sis a window of lengthninsides + s.Hint 2
There are only two alternating targets of length
n, so each window has two mismatch counts.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
- Form
t = s + s. - Walk
iovert, comparingt[i]with the pattern that has'0'at even absolute indices. Count mismatches indiff0; matches are mismatches for the other pattern, so they go todiff1. - Once
i >= n, remove indexi - nfrom whichever counter it belonged to. - From
i = n - 1onwards, the window is complete; take the minimum ofdiff0anddiff1.
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 evennthe answer is the same as without rotations. - Starting to record the answer before
i = n - 1measures 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 bestJava
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