Problem Statement
Brute Force [Accepted]
class Solution:
def removeOccurrences(self, s: str, part: str) -> str:
list_s = list(s)
while True:
curr_s = ''.join(list_s)
idx = curr_s.find(part)
if idx == -1:
break
list_s = list_s[:idx] + list_s[idx + len(part):]
return ''.join(list_s)
Editorial
Approach 1: Iteration
class Solution:
def removeOccurrences(self, s: str, part: str) -> str:
# Continue removing occurrences of 'part' as long as it exists in 's'
while part in s:
# Find the index of the leftmost occurrence of 'part'
part_start_index = s.find(part)
# Remove the substring 'part' by concatenating segments before and after 'part'
s = s[:part_start_index] + s[part_start_index + len(part) :]
# Return the updated string after all occurrences are removed
return s
Approach 2: Stack
class Solution:
def removeOccurrences(self, s: str, part: str) -> str:
stack = []
part_length = len(part)
# Iterate through each character in the string
for char in s:
# Push current character to stack
stack.append(char)
# If stack size is greater than or equal to the part length, check for match
if len(stack) >= part_length and self._check_match(
stack, part, part_length
):
# Pop the characters matching 'part' from the stack
for _ in range(part_length):
stack.pop()
# Convert stack to string with correct order
return "".join(stack)
# Helper function to check if the top of the stack matches the 'part'
def _check_match(self, stack: list, part: str, part_length: int) -> bool:
# Compare the top 'part_length' elements of the stack with 'part'
return "".join(stack[-part_length:]) == part
- time: O(n*m)
- space: O(n + m)
Approach 3: Knuth-Morris-Pratt (KMP) Algorithm
class Solution:
def removeOccurrences(self, s: str, part: str) -> str:
# Precompute KMP longest prefix-suffix array for the pattern
kmp_lps = self._compute_longest_prefix_suffix(part)
# Using list as a stack to track characters and support pattern matching
char_stack = []
# Array to store pattern matching indices during traversal
pattern_indexes = [0] * (len(s) + 1)
str_index = 0
pattern_index = 0
while str_index < len(s):
current_char = s[str_index]
char_stack.append(current_char)
if current_char == part[pattern_index]:
# Track the next pattern index when characters match
pattern_indexes[len(char_stack)] = pattern_index + 1
pattern_index += 1
if pattern_index == len(part):
# Remove entire matched pattern from stack
for _ in range(len(part)):
char_stack.pop()
# Restore pattern index for next potential match
pattern_index = (
0
if not char_stack
else pattern_indexes[len(char_stack)]
)
else:
if pattern_index != 0:
# Backtrack pattern matching using KMP LPS
str_index -= 1
pattern_index = kmp_lps[pattern_index - 1]
char_stack.pop()
else:
# Reset pattern index tracking when no match is possible
pattern_indexes[len(char_stack)] = 0
str_index += 1
# Convert remaining stack characters to result string
return "".join(char_stack)
def _compute_longest_prefix_suffix(self, pattern: str) -> list:
# Array to store the longest proper prefix which is also a suffix
lps = [0] * len(pattern)
# Initialize tracking variables for prefix and current position
current = 1
prefix_length = 0
while current < len(pattern):
# If characters match, extend the prefix length
if pattern[current] == pattern[prefix_length]:
# Store the length of matching prefix
prefix_length += 1
lps[current] = prefix_length
current += 1
# If characters don't match and we're not at the start of the pattern
elif prefix_length != 0:
# Backtrack to the previous longest prefix-suffix
prefix_length = lps[prefix_length - 1]
# If no match and no prefix to backtrack
else:
# No prefix-suffix match found
lps[current] = 0
current += 1
# Return the computed longest prefix-suffix array
return lps
- time: O(n + m)
- space: O(n + m)
