Given a binary string S of length N, the task is to find the minimum number of characters required to be deleted from the string such that no subsequence of the form “0101” exists in the string.
Examples:
Input: S = “0101101”
Output: 2
Explanation: Removing S[1] and S[5] modifies the string to 00111. Therefore, no subsequence of the type 0101 can be obtained from the given string.Input: S = “0110100110”
Output: 2
Approach: Follow the steps below to solve the problem:
- The required valid string can consist of at most three blocks of the same elements i.e. the strings can be one of the following patterns “00…0”, “11…1”, “00…01…1”, “1…10..0”, “00..01…10..0”, “1…10…01…1”.
- Count frequencies of 0s and 1s of a block using partial sum.
- Fix the starting and ending indices of blocks of 0s and 1s and determine the minimum number of characters required to be deleted by the calculated partial sums.
- Therefore, check the length of the longest string that can be obtained by removing the subsequences of the given type.
Below is the implementation of the above approach:
C++
// C++ Program to implement// the above approach#include <bits/stdc++.h>using namespace std;// Function to find minimum characters// to be removed such that no subsequence// of the form "0101" exists in the stringint findmin(string s){ int n = s.length(); int i, j, maximum = 0; // Stores the partial sums int incr[n + 1] = { 0 }; for (i = 0; i < n; i++) { // Calculate partial sums incr[i + 1] = incr[i]; if (s[i] == '0') { incr[i + 1]++; } } for (i = 0; i < n; i++) { for (j = i + 1; j < n; j++) { // Setting endpoints and // deleting characters indices. maximum = max(maximum, incr[i] + j - i + 1 - (incr[j + 1] - incr[i]) + incr[n] - incr[j + 1]); } } // Return count of deleted characters return n - maximum;}// Driver Codeint main(){ string S = "0110100110"; int minimum = findmin(S); cout << minimum << '\n';} |
Java
// Java Program to implement// the above approachimport java.io.*;class GFG{// Function to find minimum // characters to be removed // such that no subsequence// of the form "0101" exists// in the stringstatic int findmin(String s){ int n = s.length(); int i, j, maximum = 0; // Stores the partial sums int[] incr = new int[n + 1]; for (i = 0; i < n; i++) { // Calculate partial sums incr[i + 1] = incr[i]; if (s.charAt(i) == '0') { incr[i + 1]++; } } for (i = 0; i < n; i++) { for (j = i + 1; j < n; j++) { // Setting endpoints and // deleting characters indices. maximum = Math.max(maximum, incr[i] + j - i + 1 - (incr[j + 1] - incr[i]) + incr[n] - incr[j + 1]); } } // Return count of // deleted characters return n - maximum;} // Driver Codepublic static void main(String[] args){ String S = "0110100110"; int minimum = findmin(S); System.out.println(minimum);}}// This code is contributed by akhilsaini |
Python3
# Python3 Program to implement# the above approach# Function to find minimum # characters to be removed # such that no subsequence# of the form "0101" exists # in the stringdef findmin(s): n = len(s) maximum = 0 # Stores the partial sums incr = [0] * (n + 1) for i in range(0, n): # Calculate partial sums incr[i + 1] = incr[i] if (s[i] == '0'): incr[i + 1] = incr[i + 1] + 1 for i in range(0, n + 1): for j in range(i + 1, n): # Setting endpoints and # deleting characters indices. maximum = max(maximum, incr[i] + j - i + 1 - (incr[j + 1] - incr[i]) + incr[n] - incr[j + 1]) # Return count of # deleted characters return n - maximum# Driver Codeif __name__ == "__main__": S = "0110100110" minimum = findmin(S) print(minimum)# This code is contributed by akhilsaini |
C#
// C# Program to implement// the above approachusing System;class GFG{// Function to find minimum // characters to be removed // such that no subsequence// of the form "0101" exists // in the stringstatic int findmin(string s){ int n = s.Length; int i, j, maximum = 0; // Stores the partial sums int[] incr = new int[n + 1]; for (i = 0; i < n; i++) { // Calculate partial sums incr[i + 1] = incr[i]; if (s[i] == '0') { incr[i + 1]++; } } for (i = 0; i < n; i++) { for (j = i + 1; j < n; j++) { // Setting endpoints and // deleting characters indices. maximum = Math.Max(maximum, incr[i] + j - i + 1 - (incr[j + 1] - incr[i]) + incr[n] - incr[j + 1]); } } // Return count of // deleted characters return n - maximum;} // Driver Codepublic static void Main(){ string S = "0110100110"; int minimum = findmin(S); Console.WriteLine(minimum);}}// This code is contributed by akhilsaini |
Javascript
<script>// JavaScript Program to implement// the above approach// Function to find minimum characters// to be removed such that no subsequence// of the form "0101" exists in the stringfunction findmin(s){ let n = s.length; let i, j, maximum = 0; // Stores the partial sums var incr = new Array(n+1); incr.fill(0); for (i = 0; i < n; i++) { // Calculate partial sums incr[i + 1] = incr[i]; if (s[i] == '0') { incr[i + 1]++; } } for (i = 0; i < n; i++) { for (j = i + 1; j < n; j++) { // Setting endpoints and // deleting characters indices. maximum = Math.max(maximum, incr[i] + j - i + 1 - (incr[j + 1] - incr[i]) + incr[n] - incr[j + 1]); } } // Return count of deleted characters return n - maximum;}// Driver Code let S = "0110100110"; let minimum = findmin(S); document.write(minimum + '\n'); </script> |
Output:
3
Time Complexity: O(N2)
Auxiliary Space: O(N)
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!
