Remove All Occurrences of a Substring

medium stack string

Problem

You are given two strings s and part, both made of lowercase English letters. As long as s still contains part, delete the leftmost occurrence of part from s. Return whatever string is left when no occurrence remains.

The twist: deleting one occurrence can glue the characters on either side of the gap together and create a brand-new occurrence that was not there before.

Inputs = "daabcbaabcbc", part = "abc"

Output"dab"

Peel off "abc" three times: daabcbaabcbc → dabaabcbc → dababc → dab.

s (lowercase letters, max 16)

part (lowercase letters)

def remove_occurrences(s, part):
    stack = []
    k = len(part)
    for ch in s:
        stack.append(ch)
        if len(stack) >= k and ''.join(stack[-k:]) == part:
            del stack[-k:]
    return ''.join(stack)

function removeOccurrences(s, part) {
  const stack = [];
  const k = part.length;
  for (const ch of s) {
    stack.push(ch);
    if (stack.length >= k && stack.slice(-k).join("") === part) {
      stack.length -= k;
    }
  }
  return stack.join("");
}

String removeOccurrences(String s, String part) {
    StringBuilder stack = new StringBuilder();
    int k = part.length();
    for (char ch : s.toCharArray()) {
        stack.append(ch);
        int n = stack.length();
        if (n >= k && stack.substring(n - k).equals(part)) {
            stack.delete(n - k, n);
        }
    }
    return stack.toString();
}

string removeOccurrences(string s, string part) {
    string stack;
    int k = part.size();
    for (char ch : s) {
        stack.push_back(ch);
        int n = stack.size();
        if (n >= k && stack.compare(n - k, k, part) == 0) {
            stack.erase(n - k);
        }
    }
    return stack;
}

Explanation

The naive plan — find part, delete it, search again from scratch — works but wastes effort, because every deletion forces a full re-scan. The deeper issue is the seam problem: deleting an occurrence pulls the characters before and after the gap together, and they may spell part across the seam. Any correct solution must catch those late-forming matches.

A stack handles seams for free. We build the answer one character at a time: push each character of s, and after every push check whether the top k = len(part) characters of the stack spell part. If they do, pop all k of them. Popping exposes the older characters again, so anything pushed afterwards can combine with them — exactly the seam case.

Walk through s = "daabcbaabcbc", part = "abc". Pushing d, a, a, b, c makes the tail spell abc, so we pop back down to "da". The next b lands right after da — a seam join — giving "dab". The run a, a, b, c builds "dabaabc", whose tail again spells abc; popping leaves "daba". Finally b, c arrive, the tail of "dababc" matches one last time, and we end with "dab".

This is equivalent to repeatedly deleting the leftmost occurrence: the stack erases a match at the precise moment its final character arrives, so no occurrence to the left can still be waiting — matches are destroyed in exactly leftmost-first order.

Each character of s is pushed once and popped at most once, and each push triggers one comparison of at most k characters against part. That gives O(n · k) time for n = len(s), and the stack itself never holds more than n characters, so space is O(n).

Time: O(n · k) Space: O(n)