Code Implementation

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

class Solution {
public:
    string removeOccurrences(string s, string part) {
        size_t pos = s.find(part);
        while (pos != string::npos) {
            s.erase(pos, part.length());
            pos = s.find(part);
        }
        return s;
    }
};
      

class Solution {
    public String removeOccurrences(String s, String part) {
        int idx = s.indexOf(part);
        while (idx != -1) {
            s = s.substring(0, idx) + s.substring(idx + part.length());
            idx = s.indexOf(part);
        }
        return s;
    }
}
      

var removeOccurrences = function(s, part) {
    while (s.indexOf(part) !== -1) {
        s = s.replace(part, "");
    }
    return s;
};
      

Problem Description

You are given two strings: s (the input string) and part (the substring to remove). Your task is to repeatedly remove all occurrences of part from s until part no longer appears in s. Return the final string after all such removals.

• Each removal must be for a single occurrence at a time (not all at once).
• Continue this process until part cannot be found in s anymore.
• It is guaranteed that there is at least one valid way to perform the removals.
• You should not reuse or overlap removed substrings.

Thought Process

At first glance, this problem looks like a simple string replacement, but the key is that we must remove one occurrence at a time and repeat until none are left. The naive approach is to look for part in s, remove it, and repeat. However, we need to be careful with overlapping cases and efficiency for long strings.

A brute-force solution would be to use built-in string functions to find and replace part in s one at a time. For each removal, we start over and check again. This is straightforward but could be slow if the string is very large or if there are many occurrences.

To optimize, we can think in terms of a stack: as we build the result character by character, we can check if the last few characters match part. If they do, we remove them. This avoids unnecessary scanning of the whole string after every removal.

Solution Approach

Let's break down the solution into clear steps:

1. Brute-force method:
   
   • While part exists in s, remove the first occurrence by replacing it with an empty string.
   • Repeat until part is no longer found.
2. Stack-based optimization:
   
   • Initialize an empty list (or stack) to store the characters of the result.
   • Iterate through each character in s, appending it to the stack.
   • After each append, check if the last len(part) characters in the stack form part.
   • If they do, remove those characters from the stack.
   • Continue until all characters are processed.
   • Join the stack to form the final string.

For this explanation, we use the brute-force approach for clarity, as it matches the code in all four languages and is easy to understand for beginners.

• We use built-in string methods like replace (Python, JavaScript), find and erase (C++), or indexOf and substring (Java) for efficient removal.
• Each time, only the first occurrence is removed, and the process repeats until done.

Example Walkthrough

Let's use an example to see how the process works step by step.

Input: s = "daabcbaabcbc", part = "abc"

1. First iteration:
   • s contains "abc" at position 2.
   • Remove it: "daabcbaabcbc" → "dabaabcbc"
2. Second iteration:
   • s now is "dabaabcbc".
   • "abc" found at position 3.
   • Remove it: "dabaabcbc" → "dabcbc"
3. Third iteration:
   • s is now "dabcbc".
   • "abc" found at position 1.
   • Remove it: "dabcbc" → "dbc"
4. Fourth iteration:
   • s is "dbc", which does not contain "abc".
   • Stop, return "dbc".

Final Output: "dbc"

Time and Space Complexity

• Brute-force approach:
  • Each time we remove part, we scan the string for its occurrence (O(n)), and removal also takes O(n).
  • If there are up to O(n) removals (in the worst case), total time complexity can be O(n^2).
  • Space complexity is O(n) for storing the string.
• Optimized stack approach:
  • Each character is processed at most once, and removals are handled efficiently.
  • Time complexity is O(n), where n is the length of the string.
  • Space complexity is O(n) for the stack.

The brute-force solution is acceptable for small to moderate inputs, but the stack-based method is preferred for large strings.

Summary

The "Remove All Occurrences of a Substring" problem is a classic example of repeated string manipulation. The key is to remove one occurrence of the target substring at a time and repeat until none are left. The brute-force solution is simple and clear, using built-in string methods, while the stack-based approach is more efficient for large inputs. Understanding how to process strings step by step and optimize for repeated operations is a valuable skill in programming.