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

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

Run Code

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

You can also try this code with Online Python Compiler

Run Code

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