LeetCode 3922 - Minimum Flips to Make Binary String Coherent
We are given a binary string s consisting only of '0' and '1'. A string is called coherent if it does not contain either of the following patterns as a subsequence: - "011" - "110" Recall that a subsequence does not need to occupy consecutive positions.
Difficulty: 🟡 Medium
Topics: String
Solution
Problem Understanding
We are given a binary string s consisting only of '0' and '1'.
A string is called coherent if it does not contain either of the following patterns as a subsequence:
"011""110"
Recall that a subsequence does not need to occupy consecutive positions. We only need to be able to select characters in order.
In one operation, we may flip a single character:
'0' → '1''1' → '0'
The goal is to determine the minimum number of flips required to transform the given string into a coherent string.
The constraint s.length <= 10^5 immediately tells us that any solution that tries all possible flip combinations is impossible. We need a solution that runs in linear time.
The most important observation is that the forbidden patterns are subsequences, not substrings. A naive implementation that only checks adjacent characters would be incorrect. The existence of a subsequence depends on the global distribution of zeros and ones throughout the entire string.
Several edge cases are worth keeping in mind:
- Strings consisting entirely of one character are already coherent.
- Very short strings cannot contain a subsequence of length three.
- Strings containing exactly one
0or exactly one1are always coherent. - Large inputs require an
O(n)solution.
Approaches
Brute Force
A brute force approach would consider every possible set of flips and check whether the resulting string is coherent.
For a string of length n, there are 2^n possible strings obtainable through flipping positions. For each candidate string, we could test whether "011" or "110" appears as a subsequence.
This approach is correct because it explores every possible result and chooses the one requiring the fewest flips. However, it is completely impractical. Even for n = 50, the number of possibilities is already enormous.
Key Insight
Instead of thinking about flips directly, we first characterize all coherent strings.
Suppose a string contains at least two 1s.
To avoid the subsequence "011", every 0 must have at most one 1 after it. Therefore every 0 must appear after the second-to-last 1.
Similarly, if a string contains at least two 0s, then avoiding "110" implies that every 1 must appear after the second-to-last 0.
These two requirements cannot simultaneously hold when there are at least two 0s and at least two 1s. Therefore a coherent string cannot contain two or more occurrences of both digits.
Consequently:
A string is coherent if and only if it contains at most one
0or at most one1.
Once this characterization is known, the problem becomes trivial.
If the string contains ones ones and zeros zeros:
- To obtain a string with at most one
1, keep one1(if any exist) and flip all remaining ones. Cost =max(0, ones - 1). - To obtain a string with at most one
0, keep one0(if any exist) and flip all remaining zeros. Cost =max(0, zeros - 1).
The answer is the minimum of these two costs.
Approach Comparison
| Approach | Time Complexity | Space Complexity | Notes |
|---|---|---|---|
| Brute Force | O(2^n · n) | O(2^n) | Enumerates all flip combinations |
| Optimal | O(n) | O(1) | Count zeros and ones, then apply the characterization |
Algorithm Walkthrough
- Count the number of
'1'characters in the string and store it inones. - Compute
zeros = n - ones. - Compute the cost of transforming the string into one containing at most one
1.
This is done by keeping one 1 and flipping all remaining ones. The cost is:
max(0, ones - 1)
4. Compute the cost of transforming the string into one containing at most one 0.
This is done by keeping one 0 and flipping all remaining zeros. The cost is:
max(0, zeros - 1)
5. Return the smaller of the two costs.
Why it works
We proved that every coherent string must contain at most one 0 or at most one 1. Therefore every valid target string belongs to one of those two families.
For each family, the minimum number of flips is obtained by preserving one occurrence of the minority digit and flipping the rest. No other strategy can use fewer flips because every extra occurrence beyond the first must be removed.
Taking the minimum over the two families therefore yields the global optimum.
Python Solution
class Solution:
def minFlips(self, s: str) -> int:
ones = s.count("1")
zeros = len(s) - ones
cost_at_most_one_one = max(0, ones - 1)
cost_at_most_one_zero = max(0, zeros - 1)
return min(cost_at_most_one_one, cost_at_most_one_zero)
The implementation follows the algorithm exactly.
First, it counts the number of ones. The number of zeros is obtained by subtracting from the string length.
Next, it computes the cost of forcing the string to contain at most one 1. If there are k ones, then k - 1 of them must be flipped. When k is 0 or 1, no flips are needed, which is why max(0, ones - 1) is used.
The same logic is applied to zeros.
Finally, the smaller of the two costs is returned.
Go Solution
func minFlips(s string) int {
ones := 0
for _, ch := range s {
if ch == '1' {
ones++
}
}
zeros := len(s) - ones
costAtMostOneOne := 0
if ones > 1 {
costAtMostOneOne = ones - 1
}
costAtMostOneZero := 0
if zeros > 1 {
costAtMostOneZero = zeros - 1
}
if costAtMostOneOne < costAtMostOneZero {
return costAtMostOneOne
}
return costAtMostOneZero
}
The Go implementation mirrors the Python solution. The only notable difference is that Go does not have a built-in max function for integers, so the nonnegative costs are computed with simple conditional statements.
There are no concerns about integer overflow because the maximum string length is only 10^5.
Worked Examples
Example 1
Input:
s = "1010"
Counts:
| Variable | Value |
|---|---|
| ones | 2 |
| zeros | 2 |
Costs:
| Target Family | Cost |
|---|---|
At most one 1 |
2 - 1 = 1 |
At most one 0 |
2 - 1 = 1 |
Answer:
min(1, 1) = 1
Example 2
Input:
s = "0110"
Counts:
| Variable | Value |
|---|---|
| ones | 2 |
| zeros | 2 |
Costs:
| Target Family | Cost |
|---|---|
At most one 1 |
1 |
At most one 0 |
1 |
Answer:
1
Example 3
Input:
s = "1000"
Counts:
| Variable | Value |
|---|---|
| ones | 1 |
| zeros | 3 |
Costs:
| Target Family | Cost |
|---|---|
At most one 1 |
0 |
At most one 0 |
2 |
Answer:
0
The string already contains only one 1, so it is already coherent.
Complexity Analysis
| Measure | Complexity | Explanation |
|---|---|---|
| Time | O(n) | One pass is used to count ones |
| Space | O(1) | Only a few integer variables are stored |
The algorithm only needs the counts of zeros and ones. No auxiliary arrays, dynamic programming tables, or other data structures are required. Therefore the memory usage remains constant regardless of input size.
Test Cases
sol = Solution()
assert sol.minFlips("1010") == 1 # example 1
assert sol.minFlips("0110") == 1 # example 2
assert sol.minFlips("1000") == 0 # example 3
assert sol.minFlips("0") == 0 # single character
assert sol.minFlips("1") == 0 # single character
assert sol.minFlips("00") == 0 # all zeros
assert sol.minFlips("11") == 0 # all ones
assert sol.minFlips("01") == 0 # one zero and one one
assert sol.minFlips("10") == 0 # one zero and one one
assert sol.minFlips("00100") == 0 # exactly one one
assert sol.minFlips("11011") == 0 # exactly one zero
assert sol.minFlips("111000") == 2 # balanced counts
assert sol.minFlips("11110000") == 3 # larger balanced counts
assert sol.minFlips("0101010101") == 4 # alternating pattern
assert sol.minFlips("1111111111") == 0 # all ones large
assert sol.minFlips("0000000000") == 0 # all zeros large
assert sol.minFlips("111110") == 0 # exactly one zero
assert sol.minFlips("000001") == 0 # exactly one one
Test Summary
| Test | Why |
|---|---|
"1010" |
Provided example |
"0110" |
Provided example |
"1000" |
Provided example |
"0" |
Minimum length |
"1" |
Minimum length |
"00" |
All zeros |
"11" |
All ones |
"01" |
One occurrence of each digit |
"10" |
One occurrence of each digit |
"00100" |
Exactly one 1 |
"11011" |
Exactly one 0 |
"111000" |
Equal numbers of zeros and ones |
"11110000" |
Larger balanced case |
"0101010101" |
Alternating pattern |
"1111111111" |
Large all-ones case |
"0000000000" |
Large all-zeros case |
"111110" |
Already coherent via one zero |
"000001" |
Already coherent via one one |
Edge Cases
Strings of Length One
A string of length one cannot possibly contain a subsequence of length three. Therefore it is always coherent.
The implementation handles this automatically because either ones or zeros equals 1, and both computed costs become 0.
Strings Containing Only One Type of Character
Examples include "000000" and "111111".
These strings already contain no forbidden subsequences. The algorithm computes one of the costs as 0, so the final answer is correctly 0.
Strings With Exactly One Minority Character
Examples include "0001000" and "1110111".
Such strings are already coherent because they contain at most one 1 or at most one 0.
A common mistake is to search for local patterns and incorrectly conclude that flips are necessary. The counting characterization avoids this issue entirely, and the algorithm immediately returns 0.
Large Alternating Strings
A string such as "010101..." contains many opportunities to form both forbidden subsequences. A naive subsequence-checking approach could become expensive if repeated many times.
The counting solution remains efficient because it only needs the total numbers of zeros and ones, yielding linear time even when the length reaches 10^5.