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”.

Please click Like if you loved this article?

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.

See also
Construct Complete Binary Tree from its Linked List Representation

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

Please click Like if you loved this article?

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.

Please click Like if you loved this article?

Ads Blocker Image Powered by Code Help Pro
Ads Blocker Detected!!!

This website does not work properly with AdBlock. We have detected that you are using extensions to block ads. Please disable Adblocker to view the content.

Refresh