Given a binary string S of length N, the task is to find the minimum number of removals to segregate all the 0s and all the 1s such that all the 0s are before all the 1s and their count are also same.
Examples:
Input: S = 01001101
Output: 2
Explanation: If you remove the 1 at index 1 and
0 at index 6, then the string becomes 000111.Input: S = “01”
Output: 0
Approach: The problem can be solved based on the concept of prefix sum:
Instead of trying to find the minimum number of removals find the maximum length subsequence which satisfies the condition.
To do this,
- Firstly calculate prefix sum for 0s and suffix sum for 1s and
- For any index i find the maximum length of the string that can be formed using 0s from the left of i and 1s from the right of i when their count are equal.
- The maximum among these lengths, is the subsequence of maximum size satisfying the criteria.
- The remaining elements must be removed.
Follow the below steps to solve the problem:
- Store prefix count of ‘0‘ in a vector left.
- Store Suffix count of ‘1‘ in a vector right.
- Initialize a variable Max = 0.
- Run a loop from index 1 to N-1.
- Check if left[i-1] = right[i], then update, Max = max(Max, 2*right[i]).
- Return N-Max.
Below is the implementation of the above approach:
C++
|
Time Complexity: O(N)
Auxiliary Space: O(N)