Remove All Occurrences of a Substring

Remove All Occurrences of a Substring

What is this problem about?

The Remove All Occurrences of a Substring problem repeatedly removes the leftmost occurrence of a given pattern from a string until no more occurrences remain. This medium coding problem uses a stack to construct the result incrementally, detecting the pattern at the top of the stack. The string, simulation, and stack interview pattern is demonstrated.

Why is this asked in interviews?

Goldman Sachs, Microsoft, Meta, Amazon, Google, Bloomberg, and IBM ask this because the efficient approach builds the result as a stack and checks if the last len(part) characters match the pattern — avoiding O(n) string scanning per removal.

Algorithmic pattern used

Stack-based construction with suffix check. Maintain a stack (or list). For each character of s: append to stack. Check if the last len(part) characters equal part. If yes, pop those characters. Continue until all characters processed.

Example explanation

s="daabcbaabcbc", part="abc".

• Process: d,a,a,b,c → stack ends with "abc" → pop 3. Stack="daa"→wait. Actually: d,a,a,b,c → check if last 3=="abc"? "abc"? a,b,c: yes (positions 2,3,4)... checking exactly. After processing: stack="da", pop "abc", add "baabcbc"... Process continues. Final: "dbc" (after all removals).

Common mistakes candidates make

• String replacement in loop (O(n²/k) complexity).
• Not building the stack correctly before checking the suffix.
• Using find() for each removal (creates intermediate strings).
• Off-by-one in the suffix slice comparison.

Interview preparation tip

Remove All Occurrences of a Substring uses the "build and trim" stack pattern: construct the output by appending one character at a time, checking if the tail matches the pattern. This is O(n × len(part)) with no intermediate string creation. Practice similar "stack with pattern detection" problems: "remove comments from code," "evaluate expression with parentheses."