Remove All Occurrences of a Substring — Problem & Solution
Remove All Occurrences of a Substring solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.
Remove All Occurrences of a Substring is a medium coding problem on strings, simulation and stack, asked in Amazon, Adobe and Twitter interviews.
- Difficulty: Medium
- Topics: Strings, Simulation, Stack
- Asked at: Amazon, Adobe, Twitter
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
Given two strings s and part, repeatedly remove the leftmost occurrence of part from s until s no longer contains it, then return s.
Example 1
Input: s = "daabcbaabcbc", part = "abc"
Output: dab
Example 2
Input: s = "axxxxyyyyb", part = "xy"
Output: ab
Example 3
Input: s = "abc", part = "d"
Output: abc
Constraints
1 <= s.length <= 401 <= part.length <= 4Both consist of lowercase English letters.
Hints for Remove All Occurrences of a Substring
Hint 1
Push characters onto a stack one at a time.
Hint 2
After each push, check whether the top
part.lengthcharacters spellpart.Hint 3
If they do, pop them off — this handles matches that only appear after an earlier removal.
How to solve Remove All Occurrences of a Substring
Push characters onto a stack and, after each push, delete the top |part| characters if they spell part.
Approach
- For each
ch, push it; if the stack's tail equalspart, remove it.
Why it works
Removing the leftmost occurrence first is equivalent to removing each occurrence as soon as it is completed, and the stack detects occurrences that only appear after an earlier removal.
Complexity
- Time —
O(n · m) - Space —
O(n)
Pitfalls
- Repeatedly calling
replaceis simpler but quadratic in the number of removals.
Reference solution
Python
def removeOccurrences(s: str, part: str) -> str:
stack = []
m = len(part)
for ch in s:
stack.append(ch)
if len(stack) >= m and "".join(stack[-m:]) == part:
del stack[-m:]
return "".join(stack)Java
public static String removeOccurrences(String s, String part) {
StringBuilder stack = new StringBuilder();
int m = part.length();
for (int i = 0; i < s.length(); i++) {
stack.append(s.charAt(i));
if (stack.length() >= m) {
boolean match = true;
for (int j = 0; j < m; j++) {
if (stack.charAt(stack.length() - m + j) != part.charAt(j)) {
match = false;
break;
}
}
if (match) stack.setLength(stack.length() - m);
}
}
return stack.toString();
}C++
string removeOccurrences(string s, string part) {
string stk;
int m = (int) part.size();
for (char c : s) {
stk.push_back(c);
if ((int) stk.size() >= m && stk.compare(stk.size() - m, m, part) == 0) {
stk.erase(stk.size() - m);
}
}
return stk;
}JavaScript
var removeOccurrences = function(s, part) {
const stack = [];
const m = part.length;
for (let i = 0; i < s.length; i++) {
stack.push(s.charAt(i));
if (stack.length >= m) {
let match = true;
for (let j = 0; j < m; j++) {
if (stack[stack.length - m + j] !== part.charAt(j)) {
match = false;
break;
}
}
if (match) stack.length -= m;
}
}
return stack.join("");
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 515 strings problems · the whole catalogue
Learn the technique: Strings · Stack Data Structure