Remove All Occurrences of a Substring — Solution

Problem

Given a string s and a pattern string part, repeatedly remove the leftmost occurrence of part from s until it no longer appears anywhere in the string. Each removal can expose new matches since characters that were separated by the deleted span may now be adjacent.

• Input: s = "daabcbaabcbc", part = "abc"
• Output: "dab"
• Explanation: Remove "abc" at index 2, then at the newly formed index 4, then at index 3, leaving "dab".

Intuition

Each removal can create a new match at the exact boundary where the deletion happened — characters from the left side and right side of the gap may form a fresh copy of part. Scanning from the beginning every time works but re-examines ground that's already clean. The better approach processes the string left to right just once: maintain a character stack, and after every push check whether the tail of the stack spells part. If it does, pop those characters immediately and the stack is valid again without any backtracking.

Approach 1 — Repeated Search

Find the leftmost occurrence of part with a linear scan, splice it out, and repeat until no occurrence remains. Each iteration shrinks the string by len(part), so the loop runs at most n / len(part) times.

1. While part is present in s, locate the leftmost starting index.
2. Concatenate the prefix before that index with the suffix after index + len(part).
3. Assign the result back to s and repeat.
4. Return s once no occurrence remains.

1def removeOccurrences(s: str, part: str) -> str:
2    while part in s:
3        leftmost_index = s.find(part)
4        s = s[:leftmost_index] + s[leftmost_index + len(part):]
5    return s

Time: O(n² / m) — up to n/m removals each requiring an O(n) search and O(n) string copy, where n = len(s) and m = len(part).
Space: O(n) — each reconstructed string is a fresh O(n) allocation.

Approach 2 — Stack

Push characters onto a stack one at a time. After each push, check whether the top len(part) elements match part; if they do, pop all of them. The invariant is that the stack never contains a completed occurrence of part, so no second pass is needed.

1. Initialize an empty list as the stack and store part_len = len(part).
2. For each character ch in s, append ch to the stack.
3. If len(stack) >= part_len and the last part_len characters equal part, delete those characters from the stack.
4. Join the stack into a string and return it.

1def removeOccurrences(s: str, part: str) -> str:
2    stack = []
3    part_len = len(part)
4    for char in s:
5        stack.append(char)
6        # only check the tail — everything before it is already part-free
7        if len(stack) >= part_len and ''.join(stack[-part_len:]) == part:
8            del stack[-part_len:]
9    return ''.join(stack)

Time: O(n × m) — each of the n characters triggers a tail comparison of length m.
Space: O(n) — the stack holds at most n characters.

Complexity Summary

Common Mistakes

• Using a global replace instead of leftmost-only removal — str.replace(part, "") removes all non-overlapping occurrences in one pass, which is not equivalent when newly exposed matches need to be caught in subsequent iterations.
• Forgetting that pops can expose new matches — in the stack approach this is handled automatically (the next push triggers the boundary check), but in ad-hoc solutions it is easy to break out of the loop one step too early.
• Off-by-one on the tail slice — the comparison must be stack[-part_len:] not stack[-(part_len - 1):]; testing with a single-character part exposes this quickly.
• Missing the length guard — checking the tail without first verifying len(stack) >= part_len will compare against a shorter-than-expected string, causing false negatives or index errors depending on the language.
• Ignoring the no-match case — if part never appears in s, the correct answer is s unchanged; both approaches handle this naturally but manual early-exit logic can accidentally truncate the string.

Related Problems

• valid-parentheses — pop the top of the stack when a closing bracket matches the most recent open bracket
• decode-string — stack unwinds nested encoded segments in a single left-to-right pass
• asteroid-collision — stack pops elements when a collision condition fires at the current boundary
• remove-k-digits — greedy stack that pops the previous character when a smaller digit arrives
• longest-valid-parentheses — stack tracks the last unmatched index to measure valid spans