Skip to main content
Talentd

Remove All Occurrences of a Substring - Solution & Explanation

MediumStringStackSimulation10 min readAsked at: Amazon, Microsoft, Goldman Sachs +10
Practice this problem

Problem Statement

Given two strings s and part, perform the following operation on s until all occurrences of the substring part are removed:

  • Find the leftmost occurrence of the substring part and remove it from s.

Return s after removing all occurrences of part.

A substring is a contiguous sequence of characters in a string.

 

Example 1:

Input: s = "daabcbaabcbc", part = "abc"
Output: "dab"
Explanation: The following operations are done:
- s = "daabcbaabcbc", remove "abc" starting at index 2, so s = "dabaabcbc".
- s = "dabaabcbc", remove "abc" starting at index 4, so s = "dababc".
- s = "dababc", remove "abc" starting at index 3, so s = "dab".
Now s has no occurrences of "abc".

Example 2:

Input: s = "axxxxyyyyb", part = "xy"
Output: "ab"
Explanation: The following operations are done:
- s = "axxxxyyyyb", remove "xy" starting at index 4 so s = "axxxyyyb".
- s = "axxxyyyb", remove "xy" starting at index 3 so s = "axxyyb".
- s = "axxyyb", remove "xy" starting at index 2 so s = "axyb".
- s = "axyb", remove "xy" starting at index 1 so s = "ab".
Now s has no occurrences of "xy".

 

Constraints:

  • 1 <= s.length <= 1000
  • 1 <= part.length <= 1000
  • sā€‹ā€‹ā€‹ā€‹ā€‹ā€‹ and part consists of lowercase English letters.

Approach Overview

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.

Approach 1: Iterative Removal using `find` and Slicing

This approach involves iteratively searching for the 'part' inside the 's', and removing it using string slicing until no more occurrences are left.

This function uses strstr to find the first occurrence of part in s and memmove to remove it by shifting the remaining string.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n * m) where n is the length of s and m is the length of part.
Space Complexity: O(1), in-place operations are performed.

Try this approach in the editor ā†’

Approach 2: Stack-based String Reconstruction

In this approach, a stack is used to store characters of the resultant string while comparing with the part string. We check if the last few characters of the stack match the part string, and if so, roll back the stack by the length of part.

The solution builds the resultant string using a simulated stack within the original array, removing any matching part as detected.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n * m) due to checking the last part length in each iteration.
Space Complexity: O(1), as it modifies the string in place.

Try this approach in the editor ā†’

Approach 3: Default Approach

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor ā†’

Complexity Comparison

ApproachComplexity
Iterative Removal using `find` and Slicing

Time Complexity: O(n * m) where n is the length of s and m is the length of part.
Space Complexity: O(1), in-place operations are performed.

Stack-based String Reconstruction

Time Complexity: O(n * m) due to checking the last part length in each iteration.
Space Complexity: O(1), as it modifies the string in place.

Default Approachā€”

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Iterative find and slicingO(n*m*k)O(n)Simple implementation or quick prototype where readability matters more than performance
Stack-based string reconstructionO(n*m)O(n)Preferred interview solution; avoids repeated full string scans and handles cascading removals efficiently

Video Solution

Leetcode Solutions 5781. Remove All Occurrences of a Substring ā€¢ Fraz ā€¢ 17,933 views views

Watch 9 more video solutions ā†’

Frequently Asked Questions

Is Remove All Occurrences of a Substring easy or hard?
The problem is rated Medium because the naive solution is straightforward but inefficient. The challenge is recognizing the stack-based reconstruction technique that avoids repeated scans and handles cascading substring removals efficiently.
How to solve Remove All Occurrences of a Substring in O(n)?
Process the string sequentially while maintaining a stack or dynamic string builder. After appending each character, check whether the last m characters match the substring. If they match, remove them immediately. Each character is pushed and popped at most once, giving near O(n) performance in practice.
Remove All Occurrences of a Substring Python or Java solution?
In Python, developers often use a list as a stack and join it at the end for efficiency. In Java, a StringBuilder works well because it supports fast append and delete operations. Both implementations follow the same stack-based substring checking logic.
What is the best approach for Remove All Occurrences of a Substring?
The stack-based string reconstruction approach is the most efficient and interview-friendly solution. You iterate through the string once, push characters to a stack, and remove the last m characters whenever they match the substring. This avoids repeatedly scanning the entire string and keeps the algorithm close to linear time in practice.
Is Remove All Occurrences of a Substring asked at Google/Amazon/Meta?
String manipulation and substring removal patterns frequently appear in interviews at companies like Amazon, Google, and Meta. While this exact problem may vary, the stack-based substring removal pattern and incremental string reconstruction are common interview topics.
What data structure is used in Remove All Occurrences of a Substring?
A stack (or dynamic array used as a stack) is the key data structure in the optimal approach. It allows efficient push and pop operations while checking the last few characters for a substring match.
What is the time complexity of Remove All Occurrences of a Substring?
The iterative find-and-remove approach can take O(n*m*k) time where n is the string length, m is the substring length, and k is the number of removals. The stack-based simulation reduces repeated scans and runs in O(n*m) time with O(n) extra space.

Ready to solve this problem?

Practice Remove All Occurrences of a Substring with our built-in code editor and test cases.

Practice on FleetCode
Previous

Maximum Deletions on a String