Make a given Binary String non-decreasing by removing the smallest subsequence
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++ 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-decreasing
int 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 Code
int main()
{
string str = "10011";
min_length(str);
return 0;
}
// Java program for
// the above approach
import 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 program for
# the above approach
# Function to return the
# length of smallest subsequence
# required to be removed to make
# the given string non-decreasing
def 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 Code
if __name__ == '__main__':
str = "10011"
min_length(str)
# This code is contributed by SURENDRA_GENGWAR.
// C# program for
// the above approach
using System;
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[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 code
static public void Main()
{
string str = "10011";
min_length(str);
}
}
// This code is contributed by offbeat
// Javascript program for
// the above approach
// Function to return the
// length of smallest subsequence
// required to be removed to make
// the given string non-decreasing
function 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));
}
console.log( ans);
}
// Driver Code
var str = "10011";
min_length(str);
Output
1
Time Complexity: O(N)
Auxiliary Space: O(1)
Approach: Dynamic Programming
This approach focuses on maintaining the maximum length of non-decreasing subsequences while iterating through the
string.
Follow the below steps:
- Initialize dp0 & dp1 arrays of size N to store the lengths of the longest non-decreasing subsequences ending in 0 and 1 respectively.
- Set dp0[0] or dp1[0] to 1 based on whether the first character is 0 or 1.
- Iterate through the string from the second character to the end.
- Calculate the longest non-decreasing subsequence length as max(dp0[N-1], dp1[N-1]).
- Compute the minimum subsequence to remove as N – longest_non_decreasing.
- Return the minimum removal length.
Below is the implementation of the above approach :
#include <bits/stdc++.h>
using namespace std;
int min_removal_to_non_decreasing_binary(string str) {
int N = str.length();
// Initialize dp arrays
vector<int> dp0(N, 0); // Longest non-decreasing subsequence ending with '0'
vector<int> dp1(N, 0); // Longest non-decreasing subsequence ending with '1'
// Base cases
if (str[0] == '0') {
dp0[0] = 1;
} else {
dp1[0] = 1;
}
// Fill the dp arrays
for (int i = 1; i < N; ++i) {
if (str[i] == '0') {
dp0[i] = dp0[i - 1] + 1;
dp1[i] = dp1[i - 1];
} else {
dp1[i] = max(dp0[i - 1], dp1[i - 1]) + 1;
dp0[i] = dp0[i - 1];
}
}
// The longest non-decreasing subsequence length
int longest_non_decreasing = max(dp0[N - 1], dp1[N - 1]);
// The minimum subsequence to remove
int min_removal = N - longest_non_decreasing;
return min_removal;
}
// Test the function
int main() {
cout << min_removal_to_non_decreasing_binary("10011") << endl; // Output: 1
return 0;
}
// This code is contributed by Yash Agarwal
def min_removal_to_non_decreasing_binary(str):
N = len(str)
# Initialize dp arrays
dp0 = [0] * N # Longest non-decreasing subsequence ending with '0'
dp1 = [0] * N # Longest non-decreasing subsequence ending with '1'
# Base cases
if str[0] == '0':
dp0[0] = 1
else:
dp1[0] = 1
# Fill the dp arrays
for i in range(1, N):
if str[i] == '0':
dp0[i] = dp0[i-1] + 1
dp1[i] = dp1[i-1]
else:
dp1[i] = max(dp0[i-1], dp1[i-1]) + 1
dp0[i] = dp0[i-1]
# The longest non-decreasing subsequence length
longest_non_decreasing = max(dp0[N-1], dp1[N-1])
# The minimum subsequence to remove
min_removal = N - longest_non_decreasing
return min_removal
# Test the function
print(min_removal_to_non_decreasing_binary("10011"))
function min_removal_to_non_decreasing_binary(str) {
const N = str.length;
// Initialize dp arrays
let dp0 = new Array(N).fill(0); // Longest non-decreasing subsequence ending with '0'
let dp1 = new Array(N).fill(0); // Longest non-decreasing subsequence ending with '1'
// Base cases
if (str[0] === '0') {
dp0[0] = 1;
} else {
dp1[0] = 1;
}
// Fill the dp arrays
for (let i = 1; i < N; i++) {
if (str[i] === '0') {
dp0[i] = dp0[i - 1] + 1;
dp1[i] = dp1[i - 1];
} else {
dp1[i] = Math.max(dp0[i - 1], dp1[i - 1]) + 1;
dp0[i] = dp0[i - 1];
}
}
// The longest non-decreasing subsequence length
const longest_non_decreasing = Math.max(dp0[N - 1], dp1[N - 1]);
// The minimum subsequence to remove
const min_removal = N - longest_non_decreasing;
return min_removal;
}
// Test the function
console.log(min_removal_to_non_decreasing_binary("10011")); // Output: 1
// This code is contributed by Yash Agarwal
Output
1
Time Complexity: O(N)
Auxiliary Space: O(N)
Contact Us