Table of contents
1.
Introduction
2.
The Problem Statement
2.1.
Example
3.
Approach 
3.1.
Brute Force Approach
3.2.
Dynamic Programming Approach
3.3.
Algorithm
3.4.
Program
3.5.
Input
4.
Output
4.1.
Time Complexity
4.2.
Space Complexity
5.
Key Takeaways
Last Updated: Mar 27, 2024

Minimum Characters Require to Remove from Binary String to Sort it in Ascending Order

Author Ujjawal Gupta
0 upvote
Career growth poll
Do you think IIT Guwahati certified course can help you in your career?

Introduction

One day, ninja's teacher gave him an assignment in which he had to calculate the minimum characters required to remove from the binary string to sort it in ascending order. Help ninja to pass the assignment.

The above problem is the standard dynamic programming problem. Dynamic programming based-coding problems are widely asked in coding contests and various coding interviews.

In this blog, we will solve the above problem using a dynamic programming approach.

The Problem Statement

You have a binary string ‘S’ consisting of only ‘1’ and ‘0’. You have to find the count of minimum characters required to remove from the string such that the string becomes sorted.

Example

Suppose, S = ‘01011’, here we need only one character, i.e., ‘1’ from indexed 1, to be removed to sort the string. The sorted string is ‘0011’. 

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!

 

Live masterclass