Remove All Occurrences of a Substring
MedPrompt
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.
Approaches
3 approaches with complexity analysis and trade-offs.
This is a straightforward brute-force approach. We repeatedly search for the leftmost occurrence of part in s and remove it. The process continues in a loop until no more occurrences of part can be found. This method relies on standard string manipulation functions.
Algorithm
- Start a loop that continues as long as the string
scontains the substringpart. - Inside the loop, find the starting index of the leftmost occurrence of
partusing a built-in string search function (e.g.,indexOf). - If an occurrence is found at
index, create a new stringsby concatenating the part ofsbefore the occurrence (s.substring(0, index)) and the part after it (s.substring(index + part.length())). - The loop continues, re-scanning the modified string from the beginning in the next iteration.
- If no occurrence is found, the loop terminates.
- Return the final string
s.
Walkthrough
The algorithm uses a while loop that continues as long as s contains part. In each iteration, it finds the index of the first occurrence of part. A new string s is then constructed by taking the substring before the occurrence and the substring after it and concatenating them. This process repeats until part is no longer found in s. Since strings in Java are immutable, each removal operation involves creating new string objects, which can be costly in terms of time and memory, especially within a loop.
class Solution { public String removeOccurrences(String s, String part) { while (s.contains(part)) { int index = s.indexOf(part); if (index == -1) { break; } s = s.substring(0, index) + s.substring(index + part.length()); } return s; }}Complexity
Time
O(N*M*K), where N is the length of `s`, M is the length of `part`, and K is the number of occurrences removed. `s.indexOf(part)` takes O(N*M) and string concatenation takes O(N). Since K can be up to O(N), the worst-case complexity can be as high as O(N^2 * M).
Space
O(N), where N is the length of the string `s`. In each step, new strings are created for the substrings and the final concatenated string. The maximum length of these strings is N.
Trade-offs
Pros
Simple to write and understand.
Uses standard library functions, making the code concise.
Cons
Highly inefficient due to repeated string searching and object creation.
The time complexity is high, which can lead to a 'Time Limit Exceeded' error on larger inputs.
This approach improves upon the brute-force method by avoiding repeated full-string scans. We build the result string character by character using a StringBuilder. When a new character is added, we only check if the end of the current result forms the substring part. This behaves like a stack where we push characters and, if the top elements match part, we pop them.
Algorithm
- Initialize an empty
StringBuilderto act as a character stack. - Iterate through the input string
sone character at a time. - For each character, append it to the
StringBuilder. - After appending, check if the
StringBuilderhas at leastpart.length()characters. - If it does, check if the last
part.length()characters of theStringBuildermatch thepartstring. - If a match is found, delete that suffix (the last
part.length()characters) from theStringBuilder. - After iterating through all characters of
s, convert theStringBuilderto a string and return it.
Walkthrough
We use a StringBuilder to efficiently build the final string. We iterate through the input string s from left to right. For each character, we append it to our StringBuilder. After each append operation, we check if the StringBuilder is long enough to contain part and if its suffix matches part. If a match is found, we use the delete() method to remove that suffix. This process correctly simulates removing the leftmost occurrence because we process the string in order and remove any match as soon as it's formed. This avoids re-scanning the parts of the string that have already been processed and cleared of any occurrences of part.
class Solution { public String removeOccurrences(String s, String part) { StringBuilder res = new StringBuilder(); int partLen = part.length(); for (char c : s.toCharArray()) { res.append(c); if (res.length() >= partLen) { // Check if the last partLen characters match 'part' if (res.substring(res.length() - partLen).equals(part)) { res.delete(res.length() - partLen, res.length()); } } } return res.toString(); }}Complexity
Time
O(N * M), where N is the length of `s` and M is the length of `part`. We iterate through the N characters of `s`, and for each character, we might perform a string comparison of length M.
Space
O(N), where N is the length of `s`. The `StringBuilder` can grow up to a size of N in the worst case.
Trade-offs
Pros
Significantly more efficient than the brute-force approach.
Avoids re-scanning the entire string from the beginning after each removal.
Cons
The O(M) check at each step can still be a bottleneck if
partis very long.
This is the most optimal approach, which enhances the stack-like simulation by incorporating the Knuth-Morris-Pratt (KMP) string matching algorithm. The KMP algorithm allows for finding pattern occurrences in linear time. By adapting its principles, we can avoid the expensive O(M) suffix check at each step of the simulation.
Algorithm
- First, pre-process the
partstring to compute the Knuth-Morris-Pratt (KMP) Longest Proper Prefix Suffix (LPS) array. This takesO(M)time. - Initialize a character array
resCharsto build the result and an integer arraykmpStatesto store the KMP match state for each character inresChars. - Iterate through the input string
s, character by character. - For each character, add it to
resChars. - Calculate the new KMP state using the previous state, the current character, and the pre-computed LPS array. This state represents the length of the longest prefix of
partthat is a suffix of the current result. Store this state inkmpStates. - If the new state equals
M(the length ofpart), a full match is found. - Upon finding a match, simply decrease the length pointer of our result arrays by
M, effectively removing the lastMcharacters and their states. - After iterating through all of
s, construct the final string from theresCharsarray.
Walkthrough
The key to this approach is to make the check for part at the end of our intermediate string more efficient. Instead of a direct O(M) comparison, we maintain the state of a KMP match as we build our result. We first compute the KMP LPS (failure function) array for part. Then, as we process s and build the result, we also track the KMP state. The state transition for each new character is an amortized O(1) operation. When the KMP state reaches M (the length of part), it signifies a complete match. We then 'roll back' our result by M characters. This rollback is efficient as we just need to adjust a length pointer for our result arrays. This method brings the overall time complexity down to linear.
class Solution { public String removeOccurrences(String s, String part) { int n = s.length(); int m = part.length(); int[] lps = computeLPS(part); char[] resChars = new char[n]; int[] kmpStates = new int[n]; int resLen = 0; for (int i = 0; i < n; i++) { char currentChar = s.charAt(i); resChars[resLen] = currentChar; int j = (resLen == 0) ? 0 : kmpStates[resLen - 1]; while (j > 0 && currentChar != part.charAt(j)) { j = lps[j - 1]; } if (currentChar == part.charAt(j)) { j++; } kmpStates[resLen] = j; resLen++; if (j == m) { // Match found resLen -= m; } } return new String(resChars, 0, resLen); } private int[] computeLPS(String pattern) { int m = pattern.length(); int[] lps = new int[m]; int length = 0; int i = 1; while (i < m) { if (pattern.charAt(i) == pattern.charAt(length)) { length++; lps[i] = length; i++; } else { if (length != 0) { length = lps[length - 1]; } else { lps[i] = 0; i++; } } } return lps; }}Complexity
Time
O(N + M). Computing the LPS array takes O(M). The main loop iterates N times, and the KMP state transition logic inside takes amortized O(1) time per character. The total time is linear with respect to the input sizes.
Space
O(N + M). We need O(M) space for the LPS array and O(N) space for the result character array and the KMP states array.
Trade-offs
Pros
Optimal linear time complexity.
Extremely efficient for all inputs, including large strings and long patterns.
Cons
More complex to understand and implement, as it requires knowledge of the KMP algorithm.
Solutions
Solution
class Solution {public String removeOccurrences(String s, String part) { while (s.contains(part)) { s = s.replaceFirst(part, ""); } return s; }}class Solution: def removeOccurrences(self, s: str, part: str) -> str: while part in s: s = s . replace(part, '', 1) return sclass Solution {public: string removeOccurrences(string s, string part) { int m = part.size(); while (s.find(part) != -1) { s = s.erase(s.find(part), m); } return s; }};Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.