# Remove All Occurrences of a Substring
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/remove-all-occurrences-of-a-substring)
Canonical: https://scaleengineer.com/dsa/problems/remove-all-occurrences-of-a-substring
**Data structures:** String, Stack
**Companies:** [Zoho](https://scaleengineer.com/companies/zoho), [X](https://scaleengineer.com/companies/x), [Arista Networks](https://scaleengineer.com/companies/arista-networks)
---
## Problem
Given two strings `s` and `part`, perform the following operation on `s` until **all** occurrences of the substring `part` are removed:

* Find the **leftmost** occurrence of the substring `part` and **remove** it from `s`.

Return `s` _after removing all occurrences of_ `part`.

A **substring** is a contiguous sequence of characters in a string.

**Example 1:**

**Input:** s = "daabcbaabcbc", part = "abc"
**Output:** "dab"
**Explanation**: The following operations are done:
- s = "da**abc**baabcbc", remove "abc" starting at index 2, so s = "dabaabcbc".
- s = "daba**abc**bc", remove "abc" starting at index 4, so s = "dababc".
- s = "dab**abc**", 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 = "axxx**xy**yyyb", remove "xy" starting at index 4 so s = "axxxyyyb".
- s = "axx**xy**yyb", remove "xy" starting at index 3 so s = "axxyyb".
- s = "ax**xy**yb", remove "xy" starting at index 2 so s = "axyb".
- s = "a**xy**b", 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.

# Approaches
## Iterative Removal using String Manipulation
This is a straightforward brute-force approach. We repeatedly search for the leftmost occurrence of `part` in `s` and remove it. The process continues in a loop until no more occurrences of `part` can be found. This method relies on standard string manipulation functions.
**Time:** O(N*M*K), where N is the length of `s`, M is the length of `part`, and K is the number of occurrences removed. `s.indexOf(part)` takes O(N*M) and string concatenation takes O(N). Since K can be up to O(N), the worst-case complexity can be as high as O(N^2 * M). · **Space:** O(N), where N is the length of the string `s`. In each step, new strings are created for the substrings and the final concatenated string. The maximum length of these strings is N.
**Pros:** Simple to write and understand.; Uses standard library functions, making the code concise.
**Cons:** Highly inefficient due to repeated string searching and object creation.; The time complexity is high, which can lead to a 'Time Limit Exceeded' error on larger inputs.
### Explanation
The algorithm uses a `while` loop that continues as long as `s` contains `part`. In each iteration, it finds the index of the first occurrence of `part`. A new string `s` is then constructed by taking the substring before the occurrence and the substring after it and concatenating them. This process repeats until `part` is no longer found in `s`. Since strings in Java are immutable, each removal operation involves creating new string objects, which can be costly in terms of time and memory, especially within a loop.

```java
class Solution {
    public String removeOccurrences(String s, String part) {
        while (s.contains(part)) {
            int index = s.indexOf(part);
            if (index == -1) {
                break;
            }
            s = s.substring(0, index) + s.substring(index + part.length());
        }
        return s;
    }
}
```
### Algorithm
- Start a loop that continues as long as the string `s` contains the substring `part`.
- Inside the loop, find the starting index of the leftmost occurrence of `part` using a built-in string search function (e.g., `indexOf`).
- If an occurrence is found at `index`, create a new string `s` by concatenating the part of `s` before the occurrence (`s.substring(0, index)`) and the part after it (`s.substring(index + part.length())`).
- The loop continues, re-scanning the modified string from the beginning in the next iteration.
- If no occurrence is found, the loop terminates.
- Return the final string `s`.

## Simulation using a StringBuilder (Stack-like approach)
This approach improves upon the brute-force method by avoiding repeated full-string scans. We build the result string character by character using a `StringBuilder`. When a new character is added, we only check if the *end* of the current result forms the substring `part`. This behaves like a stack where we push characters and, if the top elements match `part`, we pop them.
**Time:** O(N * M), where N is the length of `s` and M is the length of `part`. We iterate through the N characters of `s`, and for each character, we might perform a string comparison of length M. · **Space:** O(N), where N is the length of `s`. The `StringBuilder` can grow up to a size of N in the worst case.
**Pros:** Significantly more efficient than the brute-force approach.; Avoids re-scanning the entire string from the beginning after each removal.
**Cons:** The O(M) check at each step can still be a bottleneck if `part` is very long.
### Explanation
We use a `StringBuilder` to efficiently build the final string. We iterate through the input string `s` from left to right. For each character, we append it to our `StringBuilder`. After each append operation, we check if the `StringBuilder` is long enough to contain `part` and if its suffix matches `part`. If a match is found, we use the `delete()` method to remove that suffix. This process correctly simulates removing the leftmost occurrence because we process the string in order and remove any match as soon as it's formed. This avoids re-scanning the parts of the string that have already been processed and cleared of any occurrences of `part`.

```java
class Solution {
    public String removeOccurrences(String s, String part) {
        StringBuilder res = new StringBuilder();
        int partLen = part.length();
        for (char c : s.toCharArray()) {
            res.append(c);
            if (res.length() >= partLen) {
                // Check if the last partLen characters match 'part'
                if (res.substring(res.length() - partLen).equals(part)) {
                    res.delete(res.length() - partLen, res.length());
                }
            }
        }
        return res.toString();
    }
}
```
### Algorithm
- Initialize an empty `StringBuilder` to act as a character stack.
- Iterate through the input string `s` one character at a time.
- For each character, append it to the `StringBuilder`.
- After appending, check if the `StringBuilder` has at least `part.length()` characters.
- If it does, check if the last `part.length()` characters of the `StringBuilder` match the `part` string.
- If a match is found, delete that suffix (the last `part.length()` characters) from the `StringBuilder`.
- After iterating through all characters of `s`, convert the `StringBuilder` to a string and return it.

## Optimized Simulation using KMP Algorithm
This is the most optimal approach, which enhances the stack-like simulation by incorporating the Knuth-Morris-Pratt (KMP) string matching algorithm. The KMP algorithm allows for finding pattern occurrences in linear time. By adapting its principles, we can avoid the expensive O(M) suffix check at each step of the simulation.
**Time:** O(N + M). Computing the LPS array takes O(M). The main loop iterates N times, and the KMP state transition logic inside takes amortized O(1) time per character. The total time is linear with respect to the input sizes. · **Space:** O(N + M). We need O(M) space for the LPS array and O(N) space for the result character array and the KMP states array.
**Pros:** Optimal linear time complexity.; Extremely efficient for all inputs, including large strings and long patterns.
**Cons:** More complex to understand and implement, as it requires knowledge of the KMP algorithm.
### Explanation
The key to this approach is to make the check for `part` at the end of our intermediate string more efficient. Instead of a direct O(M) comparison, we maintain the state of a KMP match as we build our result. We first compute the KMP LPS (failure function) array for `part`. Then, as we process `s` and build the result, we also track the KMP state. The state transition for each new character is an amortized O(1) operation. When the KMP state reaches `M` (the length of `part`), it signifies a complete match. We then 'roll back' our result by `M` characters. This rollback is efficient as we just need to adjust a length pointer for our result arrays. This method brings the overall time complexity down to linear.

```java
class Solution {
    public String removeOccurrences(String s, String part) {
        int n = s.length();
        int m = part.length();
        int[] lps = computeLPS(part);
        
        char[] resChars = new char[n];
        int[] kmpStates = new int[n];
        int resLen = 0;

        for (int i = 0; i < n; i++) {
            char currentChar = s.charAt(i);
            resChars[resLen] = currentChar;
            
            int j = (resLen == 0) ? 0 : kmpStates[resLen - 1];

            while (j > 0 && currentChar != part.charAt(j)) {
                j = lps[j - 1];
            }
            if (currentChar == part.charAt(j)) {
                j++;
            }
            
            kmpStates[resLen] = j;
            resLen++;

            if (j == m) { // Match found
                resLen -= m;
            }
        }
        return new String(resChars, 0, resLen);
    }

    private int[] computeLPS(String pattern) {
        int m = pattern.length();
        int[] lps = new int[m];
        int length = 0;
        int i = 1;
        while (i < m) {
            if (pattern.charAt(i) == pattern.charAt(length)) {
                length++;
                lps[i] = length;
                i++;
            } else {
                if (length != 0) {
                    length = lps[length - 1];
                } else {
                    lps[i] = 0;
                    i++;
                }
            }
        }
        return lps;
    }
}
```
### Algorithm
- First, pre-process the `part` string to compute the Knuth-Morris-Pratt (KMP) Longest Proper Prefix Suffix (LPS) array. This takes `O(M)` time.
- Initialize a character array `resChars` to build the result and an integer array `kmpStates` to store the KMP match state for each character in `resChars`.
- Iterate through the input string `s`, character by character.
- For each character, add it to `resChars`.
- Calculate the new KMP state using the previous state, the current character, and the pre-computed LPS array. This state represents the length of the longest prefix of `part` that is a suffix of the current result. Store this state in `kmpStates`.
- If the new state equals `M` (the length of `part`), a full match is found.
- Upon finding a match, simply decrease the length pointer of our result arrays by `M`, effectively removing the last `M` characters and their states.
- After iterating through all of `s`, construct the final string from the `resChars` array.

# Solutions
### Java

```java
class Solution {
public
  String removeOccurrences(String s, String part) {
    while (s.contains(part)) {
      s = s.replaceFirst(part, "");
    }
    return s;
  }
}

```

### Python

```python
class Solution:
    def removeOccurrences(self, s: str, part: str) -> str: while part in s: s = s . replace(part, '', 1) return s

```

### CPP

```cpp
class Solution {
public:
  string removeOccurrences(string s, string part) {
    int m = part.size();
    while (s.find(part) != -1) {
      s = s.erase(s.find(part), m);
    }
    return s;
  }
};

```