LeetCode 0926. Flip String to Monotone Increasing Solution in Java, C++, Python & More | Explanation + Code

Description

A binary string is monotone increasing if it consists of some number of 0's (possibly none), followed by some number of 1's (also possibly none).

You are given a binary string s. You can flip s[i] changing it from 0 to 1 or from 1 to 0.

Return the minimum number of flips to make s monotone increasing.

 

Example 1:

Input: s = "00110"
Output: 1
Explanation: We flip the last digit to get 00111.

Example 2:

Input: s = "010110"
Output: 2
Explanation: We flip to get 011111, or alternatively 000111.

Example 3:

Input: s = "00011000"
Output: 2
Explanation: We flip to get 00000000.

 

Constraints:

• 1 <= s.length <= 105
• s[i] is either '0' or '1'.

Solutions

Solution 1: Prefix Sum + Enumeration

First, we count the number of '0's in string s, denoted as tot. We define a variable ans for the answer, initially set ans = tot, which represents the number of flips to change all '0's to '1's.

Then, we can enumerate each position i, change all '1's to the left of position i (including i) to '0', and change all '0's to the right of position i to '1'. We calculate the number of flips in this case, which is i + 1 - cur + tot - cur, where cur represents the number of '0's to the left of position i (including i). We update the answer ans = min(ans, i + 1 - cur + tot - cur).

Finally, return the answer ans.

The time complexity is O(n), where n is the length of the string s. The space complexity is O(1).

PythonJavaC++GoTypeScriptJavaScript

class Solution: def minFlipsMonoIncr(self, s: str) -> int: tot = s.count("0") ans, cur = tot, 0 for i, c in enumerate(s, 1): cur += int(c == "0") ans = min(ans, i - cur + tot - cur) return ans(code-box)

class Solution { public int minFlipsMonoIncr(String s) { int n = s.length(); int tot = 0; for (int i = 0; i < n; ++i) { if (s.charAt(i) == '0') { ++tot; } } int ans = tot, cur = 0; for (int i = 1; i <= n; ++i) { if (s.charAt(i - 1) == '0') { ++cur; } ans = Math.min(ans, i - cur + tot - cur); } return ans; } }(code-box)

class Solution { public: int minFlipsMonoIncr(string s) { int tot = count(s.begin(), s.end(), '0'); int ans = tot, cur = 0; for (int i = 1; i <= s.size(); ++i) { cur += s[i - 1] == '0'; ans = min(ans, i - cur + tot - cur); } return ans; } };(code-box)

func minFlipsMonoIncr(s string) int { tot := strings.Count(s, "0") ans, cur := tot, 0 for i, c := range s { if c == '0' { cur++ } ans = min(ans, i+1-cur+tot-cur) } return ans }(code-box)

function minFlipsMonoIncr(s: string): number { let tot = 0; for (const c of s) { tot += c === '0' ? 1 : 0; } let [ans, cur] = [tot, 0]; for (let i = 1; i <= s.length; ++i) { cur += s[i - 1] === '0' ? 1 : 0; ans = Math.min(ans, i - cur + tot - cur); } return ans; }(code-box)

/** * @param {string} s * @return {number} */ var minFlipsMonoIncr = function (s) { let tot = 0; for (const c of s) { tot += c === '0' ? 1 : 0; } let [ans, cur] = [tot, 0]; for (let i = 1; i <= s.length; ++i) { cur += s[i - 1] === '0' ? 1 : 0; ans = Math.min(ans, i - cur + tot - cur); } return ans; };(code-box)