Remove All Occurrences of a Substring solution and explanation
IBM
Infosys
Google
TCS
9 more videos on this problem
Leetcode Solutions 5781. Remove All Occurrences of a SubstringFraz · 8:54 · 17K views
LeetCode 1910. Remove All Occurrences of a Substring - Interview Prep Ep 123Fisher Coder · 6:20 · 7K views
Remove All Occurrences of a Substring | Leetcode 1910Techdose · 17:32 · 7K views
1910. Remove All Occurrences of a Substring | Stack | KMP | 3 ApproachesAryan Mittal · 28:39 · 3K views
Leetcode 1910 Remove All Occurrences of a Substring - Fast Elegant & Clean Java SolutionAlgorithmicIQ · 8:58 · 3K views
1910. Remove All Occurrences of a Substring (Leetcode Medium)Programming Live with Larry · 5:54 · 1K views
LeetCode 1910 Remove All Occurrences of a Substring | String Matching | KMP | Asked in GoogleCode Harmony · 12:14 · 576 views
Daily Leetcode #1778: Feb 11, 2025 - 1910. Remove All Occurrences of a SubstringProgramming Live with Larry · 9:49 · 515 views
Remove All Occurrences of a Substring | LeetCode 1910 | Java Code | Developer CoderDeveloper Coder · 10:28 · 460 views
1910. Remove All Occurrences of a Substring | Leetcode Daily ChallengeEthos Typos · 8:48 · 410 views
The problem
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
partand remove it froms.
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 <= 10001 <= part.length <= 1000s andpartconsists 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.
def removeOccurrences(s: str, part: str) -> str:
while part in s:
s = s.replace(part, "", 1)
return s
s = "daabcbaabcbc"
part = "abc"
print(removeOccurrences(s, part)) # Output: dabpublic class Main {
public static String removeOccurrences(String s, String part) {
int index = s.indexOf(part);
while (index != -1) {
s = s.substring(0, index) + s.substring(index + part.length());
index = s.indexOf(part);
}
return s;
}
public static void main(String[] args) {
String s = "daabcbaabcbc";
String part = "abc";
System.out.println(removeOccurrences(s, part)); // Output: dab
}
}#include <iostream>
#include <string>
using namespace std;
string removeOccurrences(string s, string part) {
size_t found = s.find(part);
while (found != string::npos) {
s.erase(found, part.length());
found = s.find(part);
}
return s;
}
int main() {
string s = "daabcbaabcbc";
string part = "abc";
cout << removeOccurrences(s, part) << endl; // Output: dab
return 0;
}function removeOccurrences(s, part) {
let index = s.indexOf(part);
while (index !== -1) {
s = s.substring(0, index) + s.substring(index + part.length);
index = s.indexOf(part);
}
return s;
}
let s = "daabcbaabcbc";
let part = "abc";
console.log(removeOccurrences(s, part)); // Output: dab#include <stdio.h>
#include <string.h>
void removeOccurrences(char* s, const char* part) {
char* position;
int partLength = strlen(part);
while ((position = strstr(s, part)) != NULL) {
memmove(position, position + partLength, strlen(position + partLength) + 1);
}
}
int main() {
char s[] = "daabcbaabcbc";
const char* part = "abc";
removeOccurrences(s, part);
printf("%s\n", s); // Output: dab
return 0;
}using System;
class Program {
public static string RemoveOccurrences(string s, string part) {
int index = s.IndexOf(part);
while (index != -1) {
s = s.Remove(index, part.Length);
index = s.IndexOf(part);
}
return s;
}
static void Main() {
string s = "daabcbaabcbc";
string part = "abc";
Console.WriteLine(RemoveOccurrences(s, part)); // Output: dab
}
}The Python solution uses replace for string replacement, specifying a count of 1 to replace only the first occurrence in each iteration.
Time Complexity: O(n * m) where n is the length of s and m is the length of part.
Space Complexity: O(n) due to the creation of new string copies.
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.
def removeOccurrences(s: str, part: str) -> str:
stack = []
for char in s:
stack.append(char)
if len(stack) >= len(part) and ''.join(stack[-len(part):]) == part:
del stack[-len(part):]
return ''.join(stack)
s = "daabcbaabcbc"
part = "abc"
print(removeOccurrences(s, part)) # Output: dabpublic class Main {
public static String removeOccurrences(String s, String part) {
StringBuilder stack = new StringBuilder();
for (char c : s.toCharArray()) {
stack.append(c);
if (stack.length() >= part.length() &&
stack.substring(stack.length() - part.length()).equals(part)) {
stack.delete(stack.length() - part.length(), stack.length());
}
}
return stack.toString();
}
public static void main(String[] args) {
System.out.println(removeOccurrences("daabcbaabcbc", "abc")); // Output: dab
}
}#include <iostream>
#include <string>
using namespace std;
string removeOccurrences(string s, string part) {
string result = "";
for (char c : s) {
result.push_back(c);
if (result.size() >= part.size() &&
result.substr(result.size() - part.size()) == part) {
result.resize(result.size() - part.size());
}
}
return result;
}
int main() {
cout << removeOccurrences("daabcbaabcbc", "abc") << endl; // Output: dab
return 0;
}function removeOccurrences(s, part) {
const stack = [];
for (const char of s) {
stack.push(char);
if (stack.length >= part.length && stack.slice(stack.length - part.length).join('') === part)
stack.length -= part.length;
}
return stack.join('');
}
console.log(removeOccurrences("daabcbaabcbc", "abc")); // Output: dab#include <stdio.h>
#include <string.h>
void removeOccurrences(char* s, const char* part) {
int n = strlen(s);
int m = strlen(part);
int stackTop = 0;
for (int i = 0; i < n; ++i) {
s[stackTop++] = s[i];
if (stackTop >= m && strncmp(s + stackTop - m, part, m) == 0) {
stackTop -= m;
}
}
s[stackTop] = '\0';
}
int main() {
char s[] = "daabcbaabcbc";
removeOccurrences(s, "abc");
printf("%s\n", s); // Output: dab
return 0;
}using System;
using System.Text;
class Program {
public static string RemoveOccurrences(string s, string part) {
var stack = new StringBuilder();
foreach (char c in s) {
stack.Append(c);
if (stack.Length >= part.Length &&
stack.ToString(stack.Length - part.Length, part.Length) == part) {
stack.Remove(stack.Length - part.Length, part.Length);
}
}
return stack.ToString();
}
static void Main() {
Console.WriteLine(RemoveOccurrences("daabcbaabcbc", "abc")); // Output: dab
}
}A stack is maintained by appending characters, and the last sequence checked to match part, which if found, is popped.
Time Complexity: O(n), due to char-by-char processing.
Space Complexity: O(n), maintaining the dynamic result in the stack.
Approach 3: Default Approach
function removeOccurrences(s: string, part: string): string {
while (s.includes(part)) {
s = s.replace(part, '');
}
return s;
}func removeOccurrences(s string, part string) string {
for strings.Contains(s, part) {
s = strings.Replace(s, part, "", 1)
}
return s
}Complexity comparison
| Approach | Complexity |
|---|---|
| Iterative Removal using `find` and Slicing | Time Complexity: O(n * m) where n is the length of |
| Stack-based String Reconstruction | Time Complexity: O(n), due to char-by-char processing. |
| Default Approach | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Iterative find and slicing | O(n*m*k) | O(n) | Simple implementation or quick prototype where readability matters more than performance |
| Stack-based string reconstruction | O(n*m) | O(n) | Preferred interview solution; avoids repeated full string scans and handles cascading removals efficiently |
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.