Check if a string consisting only of a, b, c can be made empty by removing substring “abc” recursively

0 0 5 minutes read

Given a string S size of N consisting of characters ‘a‘, ‘b‘, and ‘c‘ only, the task is to check if the given string can be made empty by removing the string “abc” recursively or not. If found to be true, then print “Yes”. Otherwise, print “No”.

Examples:

Input: S = abcabc
Output: Yes
Explanation:
Below are the operations performed to empty the string:

Remove the substring S[3, 5] from the string modifies the string S to “abc”.

Remove the substring S[0, 2] from the string modifies the string S to “”.

After the above operations, the given string S can be made empty by removing substring “abc”. Therefore, print Yes.

Input: S = abcabcababccc
Output: No

Approach: The given problem can be solved by using a stack. The idea is to minimize the string to an empty string by removing all occurrences of the “abc”. Follow the steps below to solve the given problem:

Initialize a stack, say Stack to store the characters of the given string S.
Traverse the given string S and perform the following steps:
- If the current character is ‘a‘ or ‘b‘, then push it to the stack Stack.
- If the current character is ‘c‘ and the last two characters are ‘b‘ and ‘a‘ respectively, then pop twice from the stack.
- If the current character is ‘c‘ and the last two characters are not ‘b‘ and ‘a‘, then the given string S can not be formed.
After completing the above steps, if the stack is empty, then print “Yes”. Otherwise, print “No”.

Below is the implementation of the above approach:

C++

// C++ program for the above approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to check if the given
// string S can be made empty
string canMadeEmpty(string s, int n)
{
    // Stores the characters
    // of the string S
    stack<char> St;
 
    // Traverse the given string
    for (int i = 0; i < n; i++) {
        // If the character is c
        if (s[i] == 'c') {
 
            // If stack size is greater
            // than 2
            if (St.size() >= 2) {
 
                // Pop from the stack
                char b = St.top();
                St.pop();
                char a = St.top();
                St.pop();
 
                // Top two characters in
                // the stack should be 'b'
                // and 'a' respectively
                if (a != 'a' || b != 'b')
                    return "No";
            }
 
            // Otherwise, print No
            else
                return "No";
        }
 
        // If character is 'a' or 'b'
        // push to stack
        else
            St.push(s[i]);
    }
 
    // If stack is empty, then print
    // Yes. Otherwise print No
    if (St.size() == 0) {
        return "Yes";
    }
    else {
        return "No";
    }
}
 
// Driver Code
int main()
{
    string S = "aabcbc";
    int N = S.length();
    cout << canMadeEmpty(S, N);
 
    return 0;
}

Java

// Java program for the above approach
import java.util.*;
 
class GFG
{
 
// Function to check if the given
// String S can be made empty
static String canMadeEmpty(String s, int n)
{
   
    // Stores the characters
    // of the String S
    Stack<Character> St = new Stack<Character>();
 
    // Traverse the given String
    for (int i = 0; i < n; i++) 
    {
       
        // If the character is c
        if (s.charAt(i) == 'c') {
 
            // If stack size is greater
            // than 2
            if (St.size() >= 2) {
 
                // Pop from the stack
                char b = St.peek();
                St.pop();
                char a = St.peek();
                St.pop();
 
                // Top two characters in
                // the stack should be 'b'
                // and 'a' respectively
                if (a != 'a' || b != 'b')
                    return "No";
            }
 
            // Otherwise, print No
            else
                return "No";
        }
 
        // If character is 'a' or 'b'
        // push to stack
        else
            St.add(s.charAt(i));
    }
 
    // If stack is empty, then print
    // Yes. Otherwise print No
    if (St.size() == 0) {
        return "Yes";
    }
    else {
        return "No";
    }
}
 
// Driver Code
public static void main(String[] args)
{
    String S = "aabcbc";
    int N = S.length();
    System.out.print(canMadeEmpty(S, N));
}
}
 
// This code is contributed by Princi Singh.

Python3

# Python program for the above approach
 
# Function to check if the given
# string S can be made empty
def canMadeEmpty(s, n):
   
    # Stores the characters
    # of the string S
    st = []
     
    # Traverse the given string
    for i in range(n):
       
        # If the character is c
        if s[i] == 'c':
           
             # If stack size is greater
            # than 2
            if len(st) >= 2:
               
                # Pop from the stack
                b = st[-1]
                st.pop()
                a = st[-1]
                st.pop()
                 
                 # Top two characters in
                # the stack should be 'b'
                # and 'a' respectively
                if a != 'a' or b != 'b':
                    return "No"
                   
             # Otherwise, print No
            else:
                return "No"
               
        # If character is 'a' or 'b'
        # push to stack
        else:
            st.append(s[i])
             
    # If stack is empty, then print
    # Yes. Otherwise print No
    if len(st) == 0:
        return "Yes"
    else:
        return "No"
 
# Driver code
s = "aabcbc"
n = len(s)
print(canMadeEmpty(s, n))
 
# This code is contributed by Parth Manchanda

C#

// C# program for the above approach
using System;
using System.Collections.Generic;
 
public class GFG
{
 
// Function to check if the given
// String S can be made empty
static String canMadeEmpty(String s, int n)
{
   
    // Stores the characters
    // of the String S
    Stack<char> St = new Stack<char>();
 
    // Traverse the given String
    for (int i = 0; i < n; i++) 
    {
       
        // If the character is c
        if (s[i] == 'c') {
 
            // If stack size is greater
            // than 2
            if (St.Count >= 2) {
 
                // Pop from the stack
                char b = St.Peek();
                St.Pop();
                char a = St.Peek();
                St.Pop();
 
                // Top two characters in
                // the stack should be 'b'
                // and 'a' respectively
                if (a != 'a' || b != 'b')
                    return "No";
            }
 
            // Otherwise, print No
            else
                return "No";
        }
 
        // If character is 'a' or 'b'
        // push to stack
        else
            St.Push(s[i]);
    }
 
    // If stack is empty, then print
    // Yes. Otherwise print No
    if (St.Count == 0) {
        return "Yes";
    }
    else {
        return "No";
    }
}
 
// Driver Code
public static void Main(String[] args)
{
    String S = "aabcbc";
    int N = S.Length;
    Console.Write(canMadeEmpty(S, N));
}
}
 
// This code is contributed by shikhasingrajput

Javascript

<script>
        // JavaScript Program for the above approach
 
        // Function to check if the given
        // string S can be made empty
        function canMadeEmpty(s, n) {
            // Stores the characters
            // of the string S
            let St = [];
 
            // Traverse the given string
            for (let i = 0; i < n; i++) {
                // If the character is c
                if (s[i] == 'c') {
 
                    // If stack size is greater
                    // than 2
                    if (St.length >= 2) {
 
                        // Pop from the stack
                        let b = St[St.length - 1];
                        St.pop();
                        let a = St[St.length - 1];
                        St.pop();
 
                        // Top two characters in
                        // the stack should be 'b'
                        // and 'a' respectively
                        if (a != 'a' || b != 'b')
                            return "No";
                    }
 
                    // Otherwise, print No
                    else
                        return "No";
                }
 
                // If character is 'a' or 'b'
                // push to stack
                else
                    St.push(s[i]);
            }
 
            // If stack is empty, then print
            // Yes. Otherwise print No
            if (St.length == 0) {
                return "Yes";
            }
            else {
                return "No";
            }
        }
 
        // Driver Code
 
        let S = "aabcbc";
        let N = S.length;
        document.write(canMadeEmpty(S, N));
 
 
    // This code is contributed by Potta Lokesh
    </script>

Output:

Yes

Time Complexity: O(N)
Auxiliary Space: O(N)

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!