Check if a string can be emptied by removing all subsequences of the form “10”

Aditya Narayan Joardar
Last Updated: May 13, 2022

Introduction

In this article, we will see how to check if a string can be emptied by removing all the subsequences of the form "10". There are many ways to do so. The only thing stopping us is our imagination and the language barrier. Such problems are easy to solve as long as you can use the different tools provided by the language of your choice.

In this article, we will use the concepts of the abstract data structure- Stack. Readers with no prior knowledge of the same can learn from here Stack

Problem Statement

Given a binary string, check and return if it can be emptied or not by removing all the subsequences of the form “10”.

Example

Input_1 = “11110000”

Output = Yes

The string is emptied in the order:

11110000 => 111000 => 1100 => 10 => “”
 

Input_2 = “110001”

Output = No

The string is emptied in the order:

110001 => 1001 => 01 (this cannot be further emptied)

Approach and Explanation

The implementation shown in this article is done in Java. The basic idea of the approach is as follows:

  • Create a new stack.
  • Iterate through the string.
  • For every one encountered, push it into the stack.
  • For every 0 encountered, pop once from the stack.
  • If the stack is empty, return true; otherwise, return false.


In the code provided below, two functions have been used to show two different approaches to implementing the above steps. In one function, we use ArrayList that is provided to us in java.util package; in the other function, we use the in-built Stack provided to us in java.util package. 

The name of the function using ArrayList is boolean checkEmptyAl(). It takes in one String argument str provided by the user that needs to be checked. Inside this function, we do the following:

  • Create a new ArrayList of characters named al. 
  • Using a single for loop, we iterate through the string and extract each character using the charAt() function. We check if str.charAt(i) is equal to ‘1’ or not.
    • If we encounter a ‘1’, we push it into our ArrayList using the add() function.
    • Else we check if our ArrayList is empty or not. If it is not empty, we remove the last element using the remove() function. If it is empty, that means we have extra 0’s but no 1’s to pop. In such a case, we return false.
  • In the end, we return if our ArrayList is empty or not using the isEmpty() function.
     

The name of the function using Stack is boolean checkEmptyStk(). The function takes in one String argument str provided by the user. Inside this function, we do the following:

  • Create a Stack of characters named stack.
  • Using a single for loop, we iterate through the string and extract each character using the charAt() function. We check if str.charAt(i) is equal to ‘1’ or not.
    • If we encounter a ‘1’, we push it into our Stack using the push() function.
    • Else we check if our Stack is empty or not. If it is not empty, we pop() the last element. If it is empty, we return false.
  • In the end, we return if our stack is empty or not using the isEmpty() function.
     

Recommended: try to solve the problem yourself first before proceeding to the solution provided below.

Java implementation

import java.util.*;

public class EmptyStr {

  static boolean checkEmptyAl(String str) {

      int size = str.length();

      ArrayList<Character> al = new ArrayList<Character>();

      for (int i = 0; i < size; i++) {
          if (str.charAt(i) == '1')
              al.add(str.charAt(i));
          else if (!al.isEmpty())
              al.remove(al.size() - 1);
          else
              return false;
      }
      return al.isEmpty();
  }

  static boolean checkEmptyStk(String str) {
      
      int size = str.length();
      
      Stack<Integer> stack = new Stack<Integer>();
      for (int i = 0; i < size; i++) {
          if (str.charAt(i)  == '1') {
              stack.push(1);
          } else if (!stack.isEmpty()) {
              stack.pop();
          } else {
              return false;
          }
      }
      return stack.isEmpty();
  }

  public static void main(String[] args) {
      String str1 = "11110000";
      String str2 = "110001";

      System.out.println("Using Stack");
      if (checkEmptyStk(str1)) {
          System.out.println(str1 + " can be emptied by removing all the subsequences of 10.");
      } else {
          System.out.println(str1 + " cannot be emptied by removing all the subsequences of 10.");
      }

      if (checkEmptyStk(str2)) {
          System.out.println(str2 + " can be emptied by removing all the subsequences of 10.");
      } else {
          System.out.println(str2 + " cannot be emptied by removing all the subsequences of 10.");
      }

      System.out.println("\nUsing Array Lists");
      if (checkEmptyAl(str1)) {
          System.out.println(str1 + " can be emptied by removing all the subsequences of 10.");
      } else {
          System.out.println(str1 + " cannot be emptied by removing all the subsequences of 10.");
      }

      if (checkEmptyAl(str2)) {
          System.out.println(str2 + " can be emptied by removing all the subsequences of 10.");
      } else {
          System.out.println(str2 + " cannot be emptied by removing all the subsequences of 10.");
      }
  }
}

 

Output

Using Stack
11110000 can be emptied by removing all the subsequences of 10.
110001 cannot be emptied by removing all the subsequences of 10.

Using Array Lists
11110000 can be emptied by removing all the subsequences of 10.
110001 cannot be emptied by removing all the subsequences of 10.

Complexities 

Time Complexity

In the given implementation, we traverse the given string once and add each element into a Stack or an Array List. Thus time complexity is,

T(n) = O(N);

where N is the size of the string.

Space Complexity

In the given implementation, the Stack and Array List take auxiliary space. Thus, 

Space Complexity = O(N);

where N is the size of the Stack/Array List 

Frequently Asked Questions

  1. Can we solve this problem by checking if the number of 1’s and 0’s are equal or not?
    Ans. No, we cannot do so because we have to remove the subsequence of the form “10” in order to empty the string. The second example given in the article, 110001, has four 1’s and four 0’s, but it cannot be emptied as the last set of 1 and 0 is of the subsequence “01”.
     
  2. Why do we use the isEmpty() function in our implementation?
    Ans. We do this in order to avoid EmptyStackException. We can either use a try and catch block, but it will decrease the readability of the code. To keep the code simple, we perform the pop() function as long as the Stack is not empty.

Key Takeaways

To summarize the article, we discussed the problem of checking if a string can be emptied by removing all subsequences of the form “10”. We saw the problem statement, some examples of the problem, two valid approaches along with an explanation. We also saw the solution code, the time and space complexity, and a few FAQs.

Want to ace the coding rounds of big tech companies? Try our Attempt Unlimited Online Mock Test Series to start your preparation.
Learn various topics from Web Technologies, Programming Fundamentals, Data Structures, and Algorithms from our Library.

 

Happy Coding!

Was this article helpful ?
0 upvotes

Comments

No comments yet

Be the first to share what you think