926. Flip String to Monotone Increasing LeetCode Solution

Last updated: February 21, 2025

In this guide, you will get 926. Flip String to Monotone Increasing LeetCode Solution with the best time and space complexity. The solution to Flip String to Monotone Increasing problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Problem Statement
Complexity Analysis
Flip String to Monotone Increasing solution in C++
Flip String to Monotone Increasing solution in Java
Flip String to Monotone Increasing solution in Python
Additional Resources

926. Flip String to Monotone Increasing LeetCode Solution image

Problem Statement of Flip String to Monotone Increasing

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'.

Complexity Analysis

Time Complexity: O(n)
Space Complexity: O(1)

926. Flip String to Monotone Increasing LeetCode Solution in C++

class Solution {
 public:
  int minFlipsMonoIncr(string s) {
    // the number of characters to be flilpped to make the substring so far
    // monotone increasing
    int dp = 0;
    int count1 = 0;

    for (const char c : s)
      if (c == '0')
        // 1. Flip '0'.
        // 2. Keep '0' and flip all the previous 1s.
        dp = min(dp + 1, count1);
      else
        ++count1;

    return dp;
  }
};
/* code provided by PROGIEZ */

926. Flip String to Monotone Increasing LeetCode Solution in Java

class Solution {
  public int minFlipsMonoIncr(String s) {
    // the number of characters to be flilpped to make the substring so far
    // monotone increasing
    int dp = 0;
    int count1 = 0;

    for (final char c : s.toCharArray())
      if (c == '0')
        // 1. Flip '0'.
        // 2. Keep '0' and flip all the previous 1s.
        dp = Math.min(dp + 1, count1);
      else
        ++count1;

    return dp;
  }
}
// code provided by PROGIEZ

926. Flip String to Monotone Increasing LeetCode Solution in Python

class Solution:
  def minFlipsMonoIncr(self, s: str) -> int:
    # the number of characters to be flilpped to make the substring so far
    # monotone increasing
    dp = 0
    count1 = 0

    for c in s:
      if c == '0':
        # 1. Flip '0'.
        # 2. Keep '0' and flip all the previous 1s.
        dp = min(dp + 1, count1)
      else:
        count1 += 1

    return dp
 # code by PROGIEZ

Additional Resources

Happy Coding! Keep following PROGIEZ for more updates and solutions.

Table of Contents