Remove All Occurrences of a Substring

Leetcode Problem:

• Remove All Occurrences of a Substring

Summary

• Given a string s and a substring part, remove all occurrences of part from s

Approach

• Use a stack data structure to keep track of the characters in s and check for occurrences of part
• If part is found, remove it from the stack by popping the characters one by one.

Complexity

• O(n*m) where n is the length of s and m is the length of part

Explain

• The solution iterates over the string s and checks for occurrences of part by comparing the characters at the end of part with the characters in the stack
• If part is found, it removes it from the stack by popping the characters one by one
• The time complexity is O(n*m) because in the worst case, the stack size can be n and the number of occurrences of part can be m.

Solution Code:

class Solution {
public:
    vector st;
    string removeOccurrences(string s, string part) {
        for(int i = 0 ; i < s.size(); i++){
            st.push_back(s[i]);
            if(st.size() >= part.size()){
                bool success = true;
                for(int j = 0; j < part.size(); j++){
                    if(st[st.size()-j -1] != part[part.size() - j - 1]){
                        success = false;
                        break;
                    }
                }
                if(success){
                    for(int j = 0 ; j < part.size(); j++){
                        st.pop_back();
                    }
                }
            }
        }
        string ans = "";
        for(int i = 0 ; i < st.size(); i++){
            ans += st[i];
        }
        return ans;
    }
};