1910: Remove-All-Occurrences-of-a-Substring
Medium

table of contents

A string-comparison question!

I saw this and decided to utilise the Knuth-Morris-Pratt Algorithm that I learnt on 07/01/2025. The only modification you need to make to it is that you need to retrieve the index of the last character on the stack stack after a deletion. We do this by storing the corresponding index of every character stored onto the stack.

code

class Solution {
public:
    vector<int> generate_LPS (string &s) {
        vector<int> LPS;
        LPS.push_back(0);
        int l = 0;
        for (int i = 1; i < s.size(); ++i) {
            while(l != 0 && s[l] != s[i]) {
                l = LPS[l-1];
            }
            if (s[i] == s[l]) {
                ++l;
            }
            LPS.push_back(l);
        }
        return LPS;
    }
    string removeOccurrences(string s, string part) {
        vector<int> LPS = generate_LPS(part);
        int index = 0;
        vector<pair<char, int>> stack;
        
        for (int i = 0; i < s.size(); ++i) {
            while(index != 0 && s[i] != part[index]) {
                index = LPS[index-1];
            }
            if (s[i] == part[index]) {
                ++index;
            }

            if (index == part.size()) {
                for (int j = 0; j < index-1; ++j) {
                    stack.pop_back();
                }
                index = stack.size() == 0 ? 0 : stack[stack.size()-1].second;
            } else {
                stack.push_back({s[i], index});
            }

        }
        string ans = "";
        for (int i = 0; i < stack.size(); ++i) {
            ans += stack[i].first;
        }
        return ans;
    }
};

complexity