Last Updated: Mar 27, 2024
Difficulty: Medium

# Check if a String Consisting Only of a, b, c can be made Empty by Removing Substring “abc” Recursively

## Introduction

Strings are one of the most basic Data Structures and are one of the favorite topics of interviewers to ask about in interviews, even in top tech companies. Mastering string problems could help you solve various problems using various approaches.

In this blog, we will discuss a problem oriented around the strings. Let's discuss the problem statement to conclude an efficient solution for the problem.

## Problem Statement

In this problem, we will be given a string of length ‘n’, and our task is to determine whether we can make the length of the given string equal to 0. The string only consists of characters ‘abc’ in random order. We need to determine if we can make the length zero by recursively removing the ‘abc’.

### Example

Input

String = “abcabc”

Output

Yes, given string can be empty

Input

String = “acbbca”

Output

No, given string cannot be empty

### Approach Using Stack

We will use the stack approach to handle this problem. We will insert the characters of the given string in the stack until we find ‘c’. Once we hit the character ‘c,’ we will check whether the first two top characters in the stack are ‘b’ and ‘a’. Make sure the size of the stack is greater than 2. If both are true, we will remove the characters from the stack.

We will repeat this process until all characters are traversed n the string. In the end, if our string is empty, recursively removing the ‘abc’ means the given string can be empty.

### Algorithm

1. Initialize the stack of type char for the givens string.

2. If the string[i] is not equal to ‘c’, insert the string[i] in the stack.

3. Else, check the size of the stack.
• If the stack size is greater or equal to 2, then pop out the top element from the stack.
• Again pop out the new top from the stack.
• Check if the first top equals ‘b’ and the second top is ‘a’. If this condition is not true return false.

4. If size<2, return false.

5. Repeat the steps and sub-steps from step 2 until all characters are traversed.

6. Return ‘true’ if the stack is empty; else, return ‘false’.

### Dry Run

Input

String = “abcabc”

Empty Stack

Our first task is to check the length of the string. If the length is less than three, we will return false,

Now, after checking the length condition, we will insert the characters of a string in the stack one by one until we hit the character ‘c’.

Now after hitting the character ‘c’ in the string, we will pop out the top and second top character from the stack. If the first top is ‘b’ and the second is ‘a’. Then we will continue the iteration until we traverse the string.

Empty the string and continue the iteration.

Again, we got a ‘c’; we will check the conditions.

Empty the stack again.

We have iterated through all the characters in the string, and our stack is empty. This means a given string can be empty by recursively removing only ‘abc’.

### Implementation in C++

``````#include <bits/stdc++.h>

using namespace std;

// Function to check string can be empty or not.
bool isEmpty(string sentence) {
stack <char> checkseq;

// Checking the length of string.
if (sentence.length() < 3) {
return false;
}
/*
Pushing the characters a and b in stack.
Removing a and b if we hit c.
*/
for (int i = 0; i < sentence.length(); i++) {
if (sentence[i] != 'c') {
checkseq.push(sentence[i]);
}
else {
if (checkseq.size() >= 2) {
char first = checkseq.top();
checkseq.pop();
char second = checkseq.top();
checkseq.pop();
if (first != 'b' || second != 'a') {
return false;
}
}
else {
return false;
}
}
}

// Checking if stack is empty.
if (checkseq.empty()) {
return true;
}
return false;
}

// Driver Code
int main() {
string t = "abcabc";
if (isEmpty(t)) {
cout << "Yes, given string can be empty" << endl;
}
else {
cout << "No, given string cannot be empty" << endl;
}
return 0;
}``````

Output

### Impementation in Python

``````#  Function to check string can be empty or not.
def isStringEmpty(sentence):
stack = []

# Checking the length of string.
if(len(sentence)<3):
return False

# Pushing the characters a and b in stack.
# Removing a and b if we hit c.
for i in range(0,len(sentence)):
if(sentence[i]!='c'):
stack.append(sentence[i])
else:
if(len(stack)>=2):
first = stack[-1]
stack.pop()

second = stack[-1]
stack.pop()

if(first!='b' or second!='a'):
return False
else:
return False
# Checking if stack is empty.
if(len(stack)):
return False

return True

t = "abcabc"
if(isStringEmpty(t)):
print("Yes, given string can be empty")
else:
print("No, given string cannot be empty")``````

Output

### Complexity Analysis

The time complexity of the above approach will be O(N), where ‘N’ is the length of the string.

The space complexity of the above approach will be O(N), where ‘N’ is the size of the stack.

Check out this problem - Longest String Chain

### How to find out the string size in c++?

You need to use the string.size() method to find the size of the string.

### Stack follows which concept?

Stack follows the LIFO Last In First Out concept.

### What is a substring?

A substring is part of the original string whose all elements are present in the original string. For example, ‘abc’ is a substring of ‘abbabc’.

### How to access the top element in the stack?

We can access the top element in a stack with the top() method. We need to access the top element of the stack.top().

### How to remove the top element from the stack?

We have to use the stack.pop() method to remove the top element from the stack.

## Conclusion

In this blog, we have discussed checking whether the given string can be empty by recursively removing the substring ‘abc’. We have implemented the solution in two programming languages.

Recommended problems -

To learn more about DSA, competitive coding, and many more knowledgeable topics, please look into the guided paths on Coding Ninjas Studio. Also, you can enroll in our courses and check out the mock test and problems available. Please check out our interview experiences and interview bundle for placement preparations.

Happy Coding!

Topics covered
1.
Introduction
2.
Problem Statement
2.1.
Example
2.2.
Approach Using Stack
2.3.
Algorithm
2.4.
Dry Run
2.5.
Implementation in C++
2.6.
Impementation in Python
2.7.
Complexity Analysis
3.