Check if String can Become Empty by Recursively Deleting given Substring


Difficulty Level Medium
Frequently asked in Adobe Delhivery GE Healthcare MakeMyTrip ServiceNow Spotify UHG Optum
String

Problem Statement

In the “Check if string can become empty by recursively deleting given substring” problem we have given two strings “s” and “t”. We have to check if the given input string “s” can be deleted completely by deleting the given input sub-string “t” recursively.

Note: Given sub-string should be present in the input string.

Input Format

The first line containing a string “s” from which we delete substring “t”.

Second-line containing a string “t”.

Output Format

Print “Yes” if we delete “s” completely by deleting the given input sub-string “t”. Otherwise, print “No”.

Example

cocodede
code
Yes

Explanation: Here, delete code from this position co”code”de, then delete the remaining “code”  from the string, then the string becomes empty. So, we print “Yes”.

cocoded
code
No

Explanation: Here, delete code from this position co”code”d, then the remaining word is cod. So, we can’t delete it further that’s why the output is “No”.

Algorithm

Here we use STL functions find() and erase().

1. Traverse the input_string.

2. If find a sub-string, store it.

3. Erase the sub-string, if sub-string not found return No

4. Else, if it reaches the end, return Yes.

Implementation

C++ program for Check if String can Become Empty by Recursively Deleting given Substring

#include <bits/stdc++.h>

using namespace std;
bool CanBeEmpty(string s, string t)
{
    while(s.size()>0)
    {
        int index = s.find(t);
        if (index == -1)
        {
            break;
        }
        s.erase(index, t.size());
    }
    if(s.size() == 0)
    {
        return true;
    }
    else
    {
        return false;
    }
}
 
int main()
{
    string s,t;
    cin>>s>>t;
    if(CanBeEmpty(s,t))
    {
        cout<<"Yes";
    }
    else
    {
        cout<<"No";
    }
    return 0;
}

Java program for Check if String can Become Empty by Recursively Deleting given Substring

import java.util.Arrays;
import java.util.Scanner;

class sum {
    
    static boolean check(String s, String t) 
    { 
        while(s.length() > 0) 
        {  
            int idx = s.indexOf(t); 
            if(idx == -1) 
            { 
                break; 
            } 
            s = s.replaceFirst(t,""); 
        } 
        return(s.length() == 0); 
    }
    public static void main(String[] args) 
    {
        Scanner sr= new Scanner(System.in);
        String s = sr.next();
        String t = sr.next();
        if(check(s,t))
        {
            System.out.println("Yes");
        }
        else
        {
            System.out.println("No");
        }
    } 
}
abcabcdede
abcde
Yes

Complexity Analysis

Time Complexity

O(n^2) where n is the size of the string “s”. Here we check the substring and delete it from the string s which takes linear time for each searching and deletion for the substring “t”.

Space Complexity

O(1) because we don’t use any auxiliary space at here.