当前位置:

leetcode - 926. Flip String to Monotone Increasing

访客 2024-01-12 886 0

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: 1Explanation: We flip the last digit to get 00111.

Example 2:

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

Example 3:

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

Constraints:

1 <= s.length <= 10^5s[i] is either '0' or '1'.

Solution

Dynamic programming, dp_0 is the minimum number of flips to end with 0, and dp_1 is the number of ending with 1, then:

d p 0 = { d p 0 , if s[i] is 0 d p 0 + 1 , if s[i] is 1 d p 1 = { d p 0 + 1 , if s[i] is 0 min ⁡ ( d p 1 , d p 0 ) , if s[i] is 1 dp_0=\begin{cases} dp_0, &\text{if s[i] is 0}\\ dp_0+1, &\text{if s[i] is 1} \end{cases} \\ dp_1=\begin{cases} dp_0+1, &\text{if s[i] is 0}\\ \min(dp_1, dp_0), &\text{if s[i] is 1} \end{cases} dp0={dp0,dp0+1,if s[i] is 0if s[i] is 1dp1={dp0+1,min(dp1,dp0),if s[i] is 0if s[i] is 1

Time complexity: o ( n ) o(n) o(n)
Space complexity: o ( 1 ) o(1) o(1)

Code

class Solution:def minFlipsMonoIncr(self, s: str) -> int:dp = [0, 0]for c in s:if c == '1':dp = [dp[0] + 1, min(dp)]else:dp = [dp[0], dp[1] + 1]return min(dp)

发表评论

  • 评论列表
还没有人评论,快来抢沙发吧~