MediumNo. 0926
Flip String to Monotone Increasing — LeetCode 926 Python Solution
- Pattern
- Dynamic Programming
- Topics
- String, Dynamic Programming
- Reading time
- 2 min
- Source
- leetcode.com
The problem
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.
Example
- Input
- s = "00110"
- Output
- 1
- Explanation
- We flip the last digit to get 00111.
Python solution
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 ansComplexity
- Time
- O(n)where n is the length of the string s
- Space · auxiliary
- O(1)
Pattern: Dynamic Programming
Define a state, write the transition, and stop recomputing the same subproblem. LeetCode 926. Flip String to Monotone Increasing is filed here on both counts: the reference solution below belongs to the algorithm family this hub collects, and LeetCode tags it Dynamic Programming.
The dynamic programming guide has the Python template for the pattern and the 481 LeetCode problems that use it.
Related problems
| No. | Problem | Difficulty |
|---|---|---|
| 0010 | Regular Expression Matching | Hard |
| 0022 | Generate Parentheses | Medium |
| 0032 | Longest Valid Parentheses | Hard |
| 0044 | Wildcard Matching | Hard |
| 0072 | Edit Distance | Medium |
| 0087 | Scramble String | Hard |
Frequently asked questions
- How hard is LeetCode 926. Flip String to Monotone Increasing?
LeetCode 926. Flip String to Monotone Increasing is rated Medium on LeetCode.
- What is the time complexity of LeetCode 926. Flip String to Monotone Increasing?
The Python solution on this page runs in O(n), where n is the length of the string s.
- What is the space complexity of LeetCode 926. Flip String to Monotone Increasing?
The Python solution on this page uses O(1) auxiliary space.
- What topics does LeetCode 926. Flip String to Monotone Increasing cover?
LeetCode 926. Flip String to Monotone Increasing is tagged String and Dynamic Programming on LeetCode.