Minimum Suffix Flips — Solution in Python, Java & C++
Minimum Suffix Flips solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.
Minimum Suffix Flips is a medium coding problem on strings and greedy, asked in Amazon and Google interviews.
- Difficulty: Medium
- Topics: Strings, Greedy
- Asked at: Amazon, Google
- 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
A binary string s of length n starts as all zeros. In one operation you pick an index i and flip every bit of s from index i to the end (each 0 becomes 1 and each 1 becomes 0).
Given the binary string target of length n, return the minimum number of operations needed to turn s into target.
Example 1
Input: target = "00110"
Output: 2
Explanation: Flip from index 2 (`00111`), then from index 4 (`00110`).
Example 2
Input: target = "101"
Output: 3
Explanation: Flip from 0 (`111`), from 1 (`100`), from 2 (`101`).
Example 3
Input: target = "000"
Output: 0
Constraints
1 <= target.length <= 10^5target[i] is '0' or '1'
Hints for Minimum Suffix Flips
Hint 1
Work left to right: once a prefix matches, only flips starting later can keep it intact.
Hint 2
The bit at index
iis decided by how many flips started at or beforei.Hint 3
A flip is needed exactly where
targetchanges value — counting from an imaginary0before index 0.
How to solve Minimum Suffix Flips
Scanning left to right, the current bit of s equals the parity of the flips made so far; a new flip is forced exactly when target[i] differs from target[i − 1] (with target[−1] = 0).
Approach
- Set
prev = '0'andops = 0. - For each character
coftarget: ifc != prev, incrementopsand setprev = c. - Return
ops.
Why it works
Flips starting after i never affect index i, so after fixing indices 0…i−1 the bit at i equals the bit at i − 1 (both have seen the same flips) — which matches target[i − 1]. If target[i] differs, a flip starting exactly at i is unavoidable, and it is enough; if they agree, flipping at i would only have to be undone later. Hence every change point costs exactly one operation and nothing else does.
Complexity
- Time —
O(n) - Space —
O(1)
Pitfalls
- Forgetting that
sstarts at0: a leading1intargetcosts a flip. - Simulating the flips literally is O(n²) — too slow for 10^5.
- Counting the ones instead of the changes between neighbours.
Reference solution
Python
def minFlips(target: str) -> int:
ops = 0
prev = "0"
for c in target:
if c != prev:
ops += 1
prev = c
return opsJava
public static int minFlips(String target) {
int ops = 0;
char prev = '0';
for (int i = 0; i < target.length(); i++) {
char c = target.charAt(i);
if (c != prev) {
ops++;
prev = c;
}
}
return ops;
}C++
int minFlips(string target) {
int ops = 0;
char prev = '0';
for (char c : target) {
if (c != prev) {
ops++;
prev = c;
}
}
return ops;
}JavaScript
var minFlips = function(target) {
var ops = 0, prev = "0";
for (var i = 0; i < target.length; i++) {
if (target[i] !== prev) {
ops++;
prev = target[i];
}
}
return ops;
};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 · Greedy Algorithms