Given a binary string str of size N, the task is to find the length of the smallest subsequence such that after erasing the subsequence the resulting string will be the longest continuous non-decreasing string.
Example :
Input: str = “10011”
Output: 1
Explanation: Removal of the first occurrence of ‘1’ results in a non-decreasing subsequence, i.e “0011”.Input: str = “11110000”
Output: 4
Approach: The problem can be solved based on the following observations:
The non-decreasing subsequences can be of the following 3 types:
- Case 1 : 00000…..
- Case 2 : 11111…..
- Case 3 : 0000….111111….
Follow the given steps to solve the problem:
- Iterate over the characters of the string.
- Count the number of 0s and 1s present in the string
- To generate non-decreasing subsequences of the form “0000….”, minimum removals required is the count of 1s in the string
- To generate non-decreasing subsequences of the form “1111….”, minimum removals required is the count of 0s in the string
- To generate non-decreasing subsequences of the form “0000…1111….”, minimum removals required can be obtained using the following steps:
- Iterate over the characters of the string. Consider removing the 1s from the left and removing the 0s from the right end of the string.
- Update the minimum after each iteration.
- Finally, print the minimum removals obtained in the above three cases as the required answer.
Below is the implementation of the above approach :
C++
// C++ program for// the above approach#include <bits/stdc++.h>using namespace std;// Function to return the// length of smallest subsequence// required to be removed to make// the given string non-decreasingint min_length(string str){ // Length of the string int n = str.length(); // Count of zeros and ones int total_zeros = 0; int total_ones = 0; // Traverse the string for (int i = 0; i < n; i++) { if (str[i] == '0') total_zeros++; else total_ones++; } // Count minimum removals to // obtain strings of the form // "00000...." or "11111..." int ans = min(total_zeros, total_ones); int cur_zeros = 0, cur_ones = 0; for (char x : str) { // Increment count if (x == '0') cur_zeros++; else cur_ones++; // Remove 1s and remaining 0s ans = min(ans, cur_ones + (total_zeros - cur_zeros)); } cout << ans;}// Driver Codeint main(){ string str = "10011"; min_length(str); return 0;} |
Java
// Java program for// the above approachimport java.io.*;class GFG{ // Function to return the // length of smallest subsequence // required to be removed to make // the given string non-decreasing public static void min_length(String str) { // Length of the string int n = str.length(); // Count of zeros and ones int total_zeros = 0; int total_ones = 0; // Traverse the string for (int i = 0; i < n; i++) { if (str.charAt(i) == '0'){ total_zeros++; } else{ total_ones++; } } // Count minimum removals to // obtain strings of the form // "00000...." or "11111..." int ans = Math.min(total_zeros, total_ones); int cur_zeros = 0, cur_ones = 0; for (int i = 0; i<str.length(); i++) { // Increment count char x = str.charAt(i); if (x == '0'){ cur_zeros++; } else{ cur_ones++; } // Remove 1s and remaining 0s ans = Math.min(ans, cur_ones + (total_zeros - cur_zeros)); } System.out.println(ans); } // Driver Code public static void main (String[] args) { String str = "10011"; min_length(str); }}// This code is contributed by rohitsingh07052 |
Python3
# Python3 program for# the above approach# Function to return the# length of smallest subsequence# required to be removed to make# the given string non-decreasingdef min_length(str): # Length of the string n = len(str) # Count of zeros and ones total_zeros = 0 total_ones = 0 # Traverse the string for i in range(n): if (str[i] == '0'): total_zeros += 1 else: total_ones += 1 # Count minimum removals to # obtain strings of the form # "00000...." or "11111..." ans = min(total_zeros, total_ones) cur_zeros = 0 cur_ones = 0 for x in str: # Increment count if (x == '0'): cur_zeros += 1 else: cur_ones += 1 # Remove 1s and remaining 0s ans = min(ans, cur_ones + (total_zeros - cur_zeros)) print(ans)# Driver Codeif __name__ == '__main__': str = "10011" min_length(str) # This code is contributed by SURENDRA_GENGWAR. |
C#
// C# program for// the above approachusing System;class GFG{ // Function to return the// length of smallest subsequence// required to be removed to make// the given string non-decreasingpublic static void min_length(string str){ // Length of the string int n = str.Length; // Count of zeros and ones int total_zeros = 0; int total_ones = 0; // Traverse the string for(int i = 0; i < n; i++) { if (str[i] == '0') { total_zeros++; } else { total_ones++; } } // Count minimum removals to // obtain strings of the form // "00000...." or "11111..." int ans = Math.Min(total_zeros, total_ones); int cur_zeros = 0, cur_ones = 0; for(int i = 0; i < str.Length; i++) { // Increment count char x = str[i]; if (x == '0') { cur_zeros++; } else { cur_ones++; } // Remove 1s and remaining 0s ans = Math.Min(ans, cur_ones + (total_zeros - cur_zeros)); } Console.WriteLine(ans);}// Driver codestatic public void Main(){ string str = "10011"; min_length(str);}}// This code is contributed by offbeat |
Javascript
<script>// Javascript program for// the above approach// Function to return the// length of smallest subsequence// required to be removed to make// the given string non-decreasingfunction min_length(str){ // Length of the string var n = str.length; // Count of zeros and ones var total_zeros = 0; var total_ones = 0; // Traverse the string for (var i = 0; i < n; i++) { if (str[i] == '0') total_zeros++; else total_ones++; } // Count minimum removals to // obtain strings of the form // "00000...." or "11111..." var ans = Math.min(total_zeros, total_ones); var cur_zeros = 0, cur_ones = 0; for( var i =0; i< str.length; i++){ // Increment count if (str[i] == '0') cur_zeros++; else cur_ones++; // Remove 1s and remaining 0s ans = Math.min(ans, cur_ones + (total_zeros - cur_zeros)); } document.write( ans);}// Driver Codevar str = "10011";min_length(str);</script> |
Output
1
Time Complexity: O(N)
Auxiliary Space: O(1)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
