Check if a string can be emptied by removing all subsequences of the form “10”
Given a binary string str, the task is to check if the string can be emptied by removing all subsequences of the form “10”
Examples:
Input: str = “11011000”
Output: Yes
Explanation:Following steps are required to be performed to empty the given string “11011000” ? “111000” ? “1100” ? “10” ? “”Input: 101001
Output: No
Approach: Follow the steps below to solve the problem:
- Traverse the string and store all 1s in a Stack.
- If str[i] = 1, then store it in the stack.
- If str[i] = 0 and stack is not empty, then pop the character at the top of the stack.
- Otherwise, return false.
- If stack is empty, return true.
- Otherwise, return false
Below is the implementation of the above approach:
C++
// C++ program for // the above approach #include <bits/stdc++.h> using namespace std; // Function to find if string // is reducible to NULL bool isReducible(string str) { // Length of string int N = str.size(); // Stack to store all 1s stack< char > s; // Iterate over the characters // of the string for ( int i = 0; i < N; i++) { // If current character is 1 if (str[i] == '1' ) // Push it into the stack s.push(str[i]); else if (!s.empty()) // Pop from the stack s.pop(); else // If the stack is empty return false ; } return s.empty(); } // Driver Code int main() { string str = "11011000" ; if (isReducible(str)) cout << "Yes" ; else cout << "No" ; return 0; } |
Java
// Java program for // the above approach import java.io.*; import java.util.*; class GFG { // Function to find if string // is reducible to NULL static boolean isReducible(String str) { // Length of string int N = str.length(); // Stack to store all 1s ArrayList<Character> s = new ArrayList<Character>(); // Iterate over the characters // of the string for ( int i = 0 ; i < N; i++) { // If current character is 1 if (str.charAt(i) == '1' ) // Push it into the stack s.add(str.charAt(i)); else if (s.size() > 0 ) // Pop from the stack s.remove(s.size() - 1 ); else // If the stack is empty return false ; } if (s.size() == 0 ) { return true ; } else { return false ; } } // Driver code public static void main (String[] args) { String str = "11011000" ; if (isReducible(str)) { System.out.println( "Yes" ); } else { System.out.println( "No" ); } } } // This code is contributed by avanitrachhadiya2155 |
Python3
# Python3 program for the above approach # Function to find if string # is reducible to NULL def isReducible( Str ) : # Length of string N = len ( Str ) # Stack to store all 1s s = [] # Iterate over the characters # of the string for i in range (N) : # If current character is 1 if ( Str [i] = = '1' ) : # Push it into the stack s.append( Str [i]) elif ( len (s) > 0 ) : # Pop from the stack del s[ len (s) - 1 ] else : # If the stack is empty return False if ( len (s) = = 0 ) : return True else : return False # Driver code Str = "11011000" if (isReducible( Str )) : print ( "Yes" ) else : print ( "No" ) # This code is contributed by divyeshrabadiya07. |
C#
// C# program for // the above approach using System; using System.Collections.Generic; class GFG { // Function to find if string // is reducible to NULL static bool isReducible( string str) { // Length of string int N = str.Length; // Stack to store all 1s List< char > s = new List< char >(); // Iterate over the characters // of the string for ( int i = 0; i < N; i++) { // If current character is 1 if (str[i] == '1' ) // Push it into the stack s.Add(str[i]); else if (s.Count > 0) // Pop from the stack s.RemoveAt(s.Count - 1); else // If the stack is empty return false ; } if (s.Count == 0) { return true ; } else { return false ; } } // Driver code static void Main() { string str = "11011000" ; if (isReducible(str)) Console.WriteLine( "Yes" ); else Console.WriteLine( "No" ); } } // This code is contributed by divyesh072019. |
Javascript
<script> // Javascript program for // the above approach // Function to find if string // is reducible to NULL function isReducible(str) { // Length of string let N = str.length; // Stack to store all 1s let s = []; // Iterate over the characters // of the string for (let i = 0; i < N; i++) { // If current character is 1 if (str[i] == '1' ) // Push it into the stack s.push(str[i]); else if (s.length > 0) // Pop from the stack s.pop(); else // If the stack is empty return false ; } if (s.length == 0) { return true ; } else { return false ; } } let str = "11011000" ; if (isReducible(str)) document.write( "Yes" ); else document.write( "No" ); // This code is contributed by suresh07. </script> |
Output:
Yes
Time Complexity: O(N)
Auxiliary Space: O(N)