Welcome to Subscribe On Youtube
Formatted question description: https://leetcode.ca/all/926.html
926. Flip String to Monotone Increasing (Medium)
A string of '0's and '1's is monotone increasing if it consists of some number of '0's (possibly 0), followed by some number of '1's (also possibly 0.)
We are given a string S of '0's and '1's, and we may flip any '0' to a '1' or a '1' to a '0'.
Return the minimum number of flips to make S monotone increasing.
Example 1:
Input: "00110" Output: 1 Explanation: We flip the last digit to get 00111.
Example 2:
Input: "010110" Output: 2 Explanation: We flip to get 011111, or alternatively 000111.
Example 3:
Input: "00011000" Output: 2 Explanation: We flip to get 00000000.
Note:
1 <= S.length <= 20000Sonly consists of'0'and'1'characters.
Solution 1. Two Pass
When we separate the string into two parts, the flip count is the sum of:
- The ones at the left side
- The zeros at the right side.
So we try different separation points from left to right, and for each trial we can easily get the flip count by keeping track of the above two counts.
// OJ: https://leetcode.com/problems/flip-string-to-monotone-increasing/
// Time: O(N)
// Space: O(1)
class Solution {
public:
int minFlipsMonoIncr(string S) {
int rightZeros = 0, leftOnes = 0;
for (char c : S) if (c == '0') rightZeros++;
int ans = rightZeros;
for (char c : S) {
if (c == '1') leftOnes++;
else rightZeros--;
ans = min(ans, rightZeros + leftOnes);
}
return ans;
}
};
Solution 2. One Pass
Think in the DP way. Assume we’ve already solved the sub-problem for substring S[0..i], and the solution for it is flipCount[i].
Then we look at the next character S[i + 1].
- If it’s
1, we can simply use the solution forS[0..i], soflipCount[i + 1] = flipCount[i]. - If it’s
0, think about the options we have:- Firstly, we can choose to flip this
0to1and reuse the solution forS[0..i]. In this caseflipCount[i + 1] = flipCount[i] + 1. - What if the best solution is not to flip? Then we need to turn all
1s inS[0..i]into0. Assume the count of1s inS[0..i]isones[i], thenflipCount[i + 1] = ones[i]
Given these two options, we pick the one with smaller result.
- Firstly, we can choose to flip this
In sum:
flipCount[0] = 0
ones[0] = 0
flipCount[i + 1] = flipCount[i] (if S[i + 1] == '1')
min(flipCount[i] + 1, ones[i]) (if S[i + 1] == '0')
where 1 <= i <= N - 2
// OJ: https://leetcode.com/problems/flip-string-to-monotone-increasing/
// Time: O(N)
// Space: O(1)
// Ref: https://leetcode.com/problems/flip-string-to-monotone-increasing/discuss/189751/C%2B%2B-one-pass-DP-solution-0ms-O(n)-or-O(1)-one-line-with-explaination.
class Solution {
public:
int minFlipsMonoIncr(string S) {
int ones = 0, ans = 0;
for (char c : S) {
if (c == '1') ones++;
else ans = min(ans + 1, ones);
}
return ans;
}
};
-
class Solution { public int minFlipsMonoIncr(String S) { if (S == null || S.length() <= 1) return 0; int length = S.length(); int[][] dp = new int[length][2]; if (S.charAt(0) == '0') dp[0][1] = 1; else dp[0][0] = 1; for (int i = 1; i < length; i++) { dp[i][0] = dp[i - 1][0]; dp[i][1] = Math.min(dp[i - 1][0], dp[i - 1][1]); char c = S.charAt(i); if (c == '0') dp[i][1]++; else dp[i][0]++; } return Math.min(dp[length - 1][0], dp[length - 1][1]); } } ############ class Solution { public int minFlipsMonoIncr(String s) { int n = s.length(); int[] left = new int[n + 1]; int[] right = new int[n + 1]; int ans = Integer.MAX_VALUE; for (int i = 1; i <= n; i++) { left[i] = left[i - 1] + (s.charAt(i - 1) == '1' ? 1 : 0); } for (int i = n - 1; i >= 0; i--) { right[i] = right[i + 1] + (s.charAt(i) == '0' ? 1 : 0); } for (int i = 0; i <= n; i++) { ans = Math.min(ans, left[i] + right[i]); } return ans; } } -
// OJ: https://leetcode.com/problems/flip-string-to-monotone-increasing/ // Time: O(N) // Space: O(1) // Ref: https://leetcode.com/problems/flip-string-to-monotone-increasing/discuss/189751/C%2B%2B-one-pass-DP-solution-0ms-O(n)-or-O(1)-one-line-with-explaination. class Solution { public: int minFlipsMonoIncr(string s) { int ones = 0, ans = 0; for (char c : s) { if (c == '1') ones++; else ans = min(ans + 1, ones); } return ans; } }; -
class Solution: def minFlipsMonoIncr(self, s: str) -> int: n = len(s) left, right = [0] * (n + 1), [0] * (n + 1) ans = 0x3F3F3F3F for i in range(1, n + 1): left[i] = left[i - 1] + (1 if s[i - 1] == '1' else 0) for i in range(n - 1, -1, -1): right[i] = right[i + 1] + (1 if s[i] == '0' else 0) for i in range(0, n + 1): ans = min(ans, left[i] + right[i]) return ans ############ class Solution(object): def minFlipsMonoIncr(self, S): """ :type S: str :rtype: int """ N = len(S) P = [0] # how many ones res = float('inf') for s in S: P.append(P[-1] + int(s)) return min(P[i] + (N - P[-1]) - (i - P[i]) for i in range(len(P))) -
func minFlipsMonoIncr(s string) int { n := len(s) left, right := make([]int, n+1), make([]int, n+1) ans := math.MaxInt32 for i := 1; i <= n; i++ { left[i] = left[i-1] if s[i-1] == '1' { left[i]++ } } for i := n - 1; i >= 0; i-- { right[i] = right[i+1] if s[i] == '0' { right[i]++ } } for i := 0; i <= n; i++ { ans = min(ans, left[i]+right[i]) } return ans } func min(x, y int) int { if x < y { return x } return y } -
/** * @param {string} s * @return {number} */ var minFlipsMonoIncr = function (s) { const n = s.length; let presum = new Array(n + 1).fill(0); for (let i = 0; i < n; ++i) { presum[i + 1] = presum[i] + (s[i] == '1'); } let ans = presum[n]; for (let i = 0; i < n; ++i) { ans = Math.min(ans, presum[i] + n - i - (presum[n] - presum[i])); } return ans; };