Remove All Occurrences of a Substring

Problem Statement

Given two strings called s and part, we are tasked with removing all occurrences of the substring part from the string s. This process involves iteratively searching for the leftmost occurrence of the substring part in s and removing it each time it is found. This operation is repeated until no more occurrences of part can be found within s. The final form of the string s, after all such occurrences have been removed, is what we return. This problem is mainly about manipulating strings based on the presence of certain substrings, ensuring all instances are diligently removed.

Examples

Example 1

Input:

s = "daabcbaabcbc", part = "abc"

Output:

"dab"

Explanation:

The following operations are done:
- s = "daabcbaabcbc", remove "abc" starting at index 2, so s = "dabaabcbc".
- s = "dabaabcbc", remove "abc" starting at index 4, so s = "dababc".
- s = "dababc", remove "abc" starting at index 3, so s = "dab".
Now s has no occurrences of "abc".

Example 2

Input:

s = "axxxxyyyyb", part = "xy"

Output:

"ab"

Explanation:

The following operations are done:
- s = "axxxxyyyyb", remove "xy" starting at index 4 so s = "axxxyyyb".
- s = "axxxyyyb", remove "xy" starting at index 3 so s = "axxyyb".
- s = "axxyyb", remove "xy" starting at index 2 so s = "axyb".
- s = "axyb", remove "xy" starting at index 1 so s = "ab".
Now s has no occurrences of "xy".

Constraints

• 1 <= s.length <= 1000
• 1 <= part.length <= 1000
• s​​​​​​ and part consists of lowercase English letters.

Approach and Intuition

1. Start with the provided strings s and part.
2. The goal is to continuously search for and remove the substring part from s. The key function to utilize here might be a string search which locates the leftmost occurrence of part in s.
3. Once part is found, it should be removed, and this adjusted version of s should be the new string on which to continue searching.
4. This process repeats until part can no longer be found within s.

Examples Breakdown:

• Example 1:

  • Start with s = "daabcbaabcbc" and part = "abc".
  • In each step, locate abc, remove it, and modify s accordingly, until abc can no longer be found.
  • The modifications through steps show the progressive removal of the substring:
    • daabcbaabcbc -> dabaabcbc -> dababc -> dab

• Example 2:

  • Starting with s = "axxxxyyyyb" and part = "xy".
  • A similar approach is taken where xy is sought and sequentially removed.
  • Progressive updates:
    • axxxxyyyyb -> axxxyyyb -> axxyyb -> axyb -> ab

This iterative approach ensures that every instance of part is removed before the final string is derived. Such a strategy is comprehensively interpreted from the examples which exhibit all the steps from initial string s to the final result after all transformations.

Solutions

class Solution {
public:
    string eliminateSubsequence(string str, string sub) {
        vector<int> lps = buildLPS(sub);
        stack<char> stk;
        vector<int> matchPos(str.length() + 1, 0);
    
        for (int i = 0, j = 0; i < str.length(); i++) {
            char current = str[i];
            stk.push(current);
    
            if (current == sub[j]) {
                matchPos[stk.size()] = ++j;
    
                if (j == sub.length()) {
                    for (int k = 0; k < sub.length(); k++) stk.pop();
                    j = stk.empty() ? 0 : matchPos[stk.size()];
                }
            } else {
                if (j != 0) {
                    i--;
                    j = lps[j - 1];
                    stk.pop();
                } else {
                    matchPos[stk.size()] = 0;
                }
            }
        }
    
        string res;
        while (!stk.empty()) {
            res = stk.top() + res;
            stk.pop();
        }
    
        return res;
    }
    
private:
    vector<int> buildLPS(string p) {
        vector<int> lpsArray(p.length(), 0);
        int len = 0;
    
        for (int i = 1; i < p.length();) {
            if (p[i] == p[len]) {
                lpsArray[i++] = ++len;
            } else {
                if (len != 0) {
                    len = lpsArray[len - 1];
                } else {
                    lpsArray[i++] = 0;
                }
            }
        }
    
        return lpsArray;
    }
};