Remove All Occurrences of a Substring - Solution & Explanation

Problem Overview: Given two strings s and part, repeatedly remove the leftmost occurrence of part from s until the substring no longer appears. The result is the final string after all deletions. The main challenge is handling cascading removals where deleting one occurrence exposes another.

Approach 1: Iterative Removal using find and Slicing (Time: O(n*m*k), Space: O(n))

This method repeatedly searches for part inside s using a substring search operation such as find(). When a match is found, remove it by slicing the string: keep the prefix before the match and append the suffix after it. Continue the loop until find() returns -1. Each iteration scans the string again, and multiple removals can occur, so the worst-case complexity grows with the number of deletions. The approach is simple and readable, making it a good baseline solution when implementing quick string manipulation logic.

Approach 2: Stack-based String Reconstruction (Time: O(n*m), Space: O(n))

This approach builds the result incrementally using a stack-like structure. Iterate through each character in s and push it onto a stack (or append to a result string builder). After each insertion, check whether the last m characters match part. If they match, pop those characters from the stack. This simulates removing the substring immediately when it appears, preventing repeated full-string scans. The check is done only when the stack length is at least m, keeping the process efficient. This technique is a classic pattern in string processing problems where deletions may trigger new matches.

The stack reconstruction behaves like a streaming algorithm: characters are processed once, and removals happen locally at the stack top. Because of this, each character is pushed and popped at most once, giving near-linear behavior in practice. Many solutions implement the stack using a mutable string builder or array for faster append and pop operations.

Recommended for interviews: The stack-based solution is typically what interviewers expect. It demonstrates understanding of incremental processing and avoids repeated full scans of the string. Mentioning the simple find + slicing approach first shows you recognize the brute-force simulation, but implementing the stack-based reconstruction shows stronger algorithmic thinking and familiarity with simulation-style problems.