Check if a String can be Emptied by Removing all Subsequences of the Form “10”

Approach

The approach is quite simple if you are familiar with the stack data structure. In this approach, we just need to push the element if it is '1' and pop if the element is '0' and the stack is not empty. One more case arises that if '0' is the first element (empty stack), it returns false because it will never be followed by '1' to form '10'. To find the result, you must check the formed stack size. If the size is equal to '0', then the result is true, else false. Let's discuss the algorithm we will use according to this approach. 

Algorithm

The steps to be performed for the above approach are as follows:

• Create a new stack.
• Iterate through the string using a for loop. 
  • If string[i] == '1', push it into the stack.
  • If string[i] == ‘0’
    • If the stack is empty, return false. 
    • Else pop ‘1’ from the stack.
• If the stack is empty, return true.
• Else return false.

Dry Run

Let's understand the algorithm using an example. For this example, input string = "110010". Let's go through each step one by one. 

Step-1

In step-1, the value of i will be 0, and at i=0, str[0] is equal to 1, so will push it into the stack. And increment the value of i.

Step-2

In this step, i will be equal to 1, and again we will encounter 1, so we will push it into the stack.
 

Step-3

In this step, i will be equal to 2, so str[i] will be equal to 0, and when we encounter 0, we will check if the stack is empty or not. In this case, the stack is not empty so we will pop the top element of the stack, and increment the value of i.
 

Step-4

Here i will be 3, so str[i] will be equal to 0, so again we will repeat the above step we will, pop the top element of the stack, and increment the value of i.

Step-5

Here in this step, i will be 4, and str[i] will be 1, so we will push it in the stack and increment i.

Step-6

This is the last step, and here str[i] will be 0, so we will pop the top element of the stack.

After the above step, the loop will be over, and we will see that stack is empty, this means that all subsequences of “10” have been removed from the string and the string has become empty. 

Implementation in C++

#include <iostream>
#include <stack>
#include <vector>
using namespace std;

// function to check if string can be emptied or not
bool checkIfStrCanBeEmpty(string str)
{
    int size = str.length();

    // Declare stack
    stack<int> stk;
   
    // Iterate through the string
    for (int i = 0; i < size; i++)
    {
        if (str[i] == '1')
            stk.push(1);
        else if (!stk.empty())
            stk.pop();
        else
            return false;
    }
    return stk.empty();
}

int main()
{
    // Declare two strings
    string str1 = "11110000";
    string str2 = "110001";

    // Check for string 1
    if (checkIfStrCanBeEmpty(str1))
        cout << str1 << " can be emptied" << endl;
    else
        cout << str1 << " cannot be emptied" << endl;

    // Check for string 2
    if (checkIfStrCanBeEmpty(str2))
        cout << str2 << " can be emptied" << endl;
    else
        cout << str2 << " cannot be emptied" << endl;
}

You can also try this code with Online C++ Compiler

Run Code

Output

Using Stack
11110000 can be emptied
110001 cannot be emptied

You can also try this code with Online Java Compiler

Run Code

Implementation in Java

import java.util.Stack;

public class Main {

    // function to check if string can be emptied or not
    public static boolean checkIfStrCanBeEmpty(String str) {
        int size = str.length();

        // Declare stack
        Stack<Integer> stk = new Stack<>();

        // Iterate through the string
        for (int i = 0; i < size; i++) {
            if (str.charAt(i) == '1')
                stk.push(1);
            else if (!stk.empty())
                stk.pop();
            else
                return false;
        }
        return stk.empty();
    }

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

        // Check for string 1
        if (checkIfStrCanBeEmpty(str1))
            System.out.println(str1 + " can be emptied");
        else
            System.out.println(str1 + " cannot be emptied");

        // Check for string 2
        if (checkIfStrCanBeEmpty(str2))
            System.out.println(str2 + " can be emptied");
        else
            System.out.println(str2 + " cannot be emptied");
    }
}

You can also try this code with Online Java Compiler

Run Code

Output

11110000 can be emptied
110001 cannot be emptied

You can also try this code with Online Python Compiler

Run Code

Implementation in Python

# function to check if string can be emptied or not
def checkIfStrCanBeEmpty(str):
    size = len(str)

    # Declare stack
    stk = []

    # Iterate through the string
    for i in range(size):
        if str[i] == '1':
            stk.append(1)
        elif stk:
            stk.pop()
        else:
            return False
    return not stk


# Declare two strings
str1 = "11110000"
str2 = "110001"

# Check for string 1
if checkIfStrCanBeEmpty(str1):
    print(str1 + " can be emptied")
else:
    print(str1 + " cannot be emptied")

# Check for string 2
if checkIfStrCanBeEmpty(str2):
    print(str2 + " can be emptied")
else:
    print(str2 + " cannot be emptied")

You can also try this code with Online Python Compiler

Run Code

Output

11110000 can be emptied
110001 cannot be emptied

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 = O(N), where N is the size of the input string.

Space Complexity

The Stack and Array List take up auxiliary space in the given implementation. Thus, Space Complexity = O(N), where N is the size of the Stack or the Array List used. 

Check out this problem - Next Smaller Element

Frequently Asked Questions

What is the difference between an array and a string?

The main difference is that an array is a data structure while a string is an object. The array can hold any data type, while strings only have character data types. Arrays can be changed, which means they are mutable, while strings are not.

What are the different operations of the stack?

Different operations to be performed on a stack include: push, pop, peek, isEmpty, and size. 

Can we solve this problem by checking whether the number of 1s and 0s are equal?

No, we cannot do so because we have to remove the form "10" subsequence to empty the string. The second example 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".

Will an empty string be considered a substring?

Yes, empty strings are also considered substrings. 

Why do we use the isEmpty() function in our implementation?

We do this in order to avoid the 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.

Conclusion

To summarise 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, and two valid approaches, along with an explanation. We also saw the solution code, the time and space complexity, and FAQs.

Recommended problems -

• Beautiful String
• Subsequence of a String
• Find the Shortest Substring in a String

Here are a few related articles you can refer to

• Boats to save people
• Add two numbers represented by Stacks
• Reverse the string using a stack
• Check if an array is stack sortable

Please refer to our guided paths on Coding Ninjas Studio to learn more about DSA, Competitive Programming, JavaScript, System Design, etc. Also, enroll in our courses and refer to the mock test and problems available. Have a look at the interview experiences and interview bundle for placement preparations.

Keep Coding.