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. 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 without prior knowledge of the same can learn about stack from here.

Problem Statement

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

Example

Input

Output

Yes

Explanation

The string is emptied in the order given in the above image.

Input

Output

No

Explanation

No operations cannot be performed further because, in the end, “01” is left, and we cannot remove “01” because we are only allowed to remove “10” subsequences.

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;
}

Output

Using Stack
11110000 can be emptied
110001 cannot be emptied

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");
}
}

Output

11110000 can be emptied
110001 cannot be emptied

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")

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.

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.