Approach
Brute Force Approach
The naive approach to solve the above problem is to take each subsequence of string ‘S’ and check whether the subsequence is sorted or not. The string with maximum length is taken out of all strings formed. The minimum number of characters required to be removed to sort the string is the difference between the size of string ‘S’ and the maximum length valid string.
Dynamic Programming Approach
The above problem can be solved using a dynamic programming approach. Apply dynamic programming to store the number of deletions required to sort the string till each index of string ‘S’. For each index, if S[i] = ’0’, then to sort the substring from index 0 to ‘i’, either delete that ‘0’, then the result is the same as the previous substring result + 1 or take that ‘0’, in this case the total deletions required is the count of ‘1’ till that index. If S[i] = ’1’, then the number of deletions upto that index is the same as the previous one because adding ‘1’ will result in a string which is already in sorted order.
The algorithm for the dynamic programming is as follows:
Algorithm
-
Define a function getMinCount():
-
Function details:
- Pass string ‘S’ as a parameter.
- This function returns the count of minimum deletions required to sort the string.
-
Working:
- Declare variable ‘ COUNT_ONE ’ and initialize it to 0.
- Create a vector of integers ‘DP’ to store the answer for each string index.
-
Iterate loop over the string:
- If S[i] == ’0’:
- DP[i + 1]=min(COUNT_ONE , DP[i] + 1).
- Else
- COUNT_ONE += 1.
- DP[i + 1] = DP[i]+1.
- Return DP[S.SIZE()].
- Call the above function in the main function.
Program
#include <iostream>
#include <vector>
using namespace std;
// Function to find the count of minimum characters to be removed to sort a binary string.
int getMinCount(string &s)
{
// Create variable to store the count of '1'.
int countOne = 0;
// Creating ‘DP’ vector.
vector<int> dp(s.length() + 1, 0);
for (int i = 0; i < s.length(); i++)
{
if (s[i] == '0')
{
dp[i + 1] = min(countOne, dp[i] + 1);
}
else
{
countOne++;
dp[i + 1] = dp[i];
}
}
return dp[s.length()];
}
int main()
{
// Taking string as an input.
string s;
cin >> s;
// Call function and assign its value to a variable 'ANS'.
int ans = getMinCount(s);
// Print 'ANS'.
cout << ans;
return 0;
}

You can also try this code with Online C++ Compiler
Run Code
Input
101000001
Output
2
Time Complexity
O(N), where ‘N’ is the size of the string.
Because traversing of string takes O(N) time.
Space Complexity
O(N), where ‘N’ is the size of the string.
Creating a vector of size ‘N’ takes O(N) space.
Key Takeaways
In this blog, we learned about an interesting problem, namely minimum characters required to be removed to sort binary strings in ascending order. We solved the problem efficiently using a dynamic programming approach. We discussed the brute approach and efficient approach and appreciated the difference in the time complexity.
Hence learning never stops, and there is a lot more to learn.
Recommended Problems -
So head over to our practice platform Coding Ninjas Studio to practice top problems, attempt mock tests, read interview experiences, and much more. Till then, Happy Coding!