LeetCode 1910 - Remove All Occurrences of a Substring

LeetCode Problem 1910

Difficulty: 🟡 Medium
Topics: String, Stack, Simulation

Solution

Problem Understanding

The problem asks us to repeatedly remove occurrences of a substring part from a string s. The important detail is that on every operation, we must remove the leftmost occurrence of part. We continue performing removals until part no longer appears anywhere inside s.

In simpler terms, we scan the string, remove one matching substring at a time, and keep doing this until the string no longer contains the target pattern.

For example, if:

s = "daabcbaabcbc"
part = "abc"

the first "abc" appears starting at index 2, so removing it produces:

"dabaabcbc"

After the removal, new occurrences may appear because characters that were previously separated can now become adjacent. This is the key challenge in the problem.

The input consists of two lowercase English strings:

• s, the original string
• part, the substring we repeatedly remove

The output is the final string after all removals are complete.

The constraints are:

1 <= s.length <= 1000
1 <= part.length <= 1000

These limits are relatively small, which means even moderately inefficient solutions may pass. However, the problem is designed to reward a cleaner and more efficient simulation approach.

Several edge cases are important:

• Removing one occurrence may create another occurrence across the boundary.
• part may overlap with itself.
• The entire string may disappear.
• part may never appear at all.
• part could be length 1, which means every matching character must be removed.

A naive implementation can easily become inefficient if it repeatedly scans and rebuilds strings.

Approaches

Brute Force Approach

The most direct solution is to repeatedly search for the leftmost occurrence of part inside s.

At each iteration:

1. Find the index of part in s
2. If no occurrence exists, stop
3. Otherwise, remove that substring
4. Repeat

In Python, this can be implemented using find() and string slicing.

This approach is correct because it exactly follows the rules described in the problem statement. Every iteration removes the leftmost occurrence until none remain.

However, repeatedly searching and rebuilding strings can become expensive. Each search may take O(n) time, and each removal creates a new string of size O(n). In the worst case, we may perform many removals.

Optimal Stack-Based Approach

The key observation is that we only need to check whether the most recently built portion of the string ends with part.

Instead of repeatedly rescanning the entire string, we process characters one by one and build the answer incrementally using a stack-like structure.

For every character:

1. Append it to the current result
2. Check whether the end of the current result matches part
3. If it does, remove those characters immediately

This works because any new occurrence created by previous removals must appear near the boundary where new characters were added.

By continuously maintaining a valid partial result, we avoid repeated full-string rescanning.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n²)	O(n)	Repeatedly searches and rebuilds strings
Optimal	O(n × m)	O(n)	Uses a stack and checks only recent characters

Here:

• n = len(s)
• m = len(part)

Because constraints are only 1000, the stack solution is easily fast enough.

Algorithm Walkthrough

Optimal Stack-Based Algorithm

1. Create an empty stack structure.

We use the stack to store the characters of the current processed string. This allows efficient append and removal operations. 2. Iterate through each character in s.

We process the input left to right because the problem always removes the leftmost occurrence first. 3. Append the current character to the stack.

This simulates building the resulting string incrementally. 4. After appending, check whether the end of the stack matches part.

Since only newly appended characters can create a new occurrence, we only need to compare the suffix of the current stack with part. 5. If the suffix matches part, remove the last len(part) characters.

This simulates removing the substring immediately once it appears. 6. Continue processing until all characters are handled. 7. Join the remaining stack characters into the final string and return it.

Why it works

The algorithm maintains an invariant:

After processing each character, the stack contains the correct string after removing all occurrences of part from the processed prefix.

Whenever a new occurrence of part appears, it must end at the current character because earlier occurrences would already have been removed. By immediately deleting matching suffixes, the stack always remains valid.

This guarantees that the final stack is exactly the desired answer.

Python Solution

class Solution:
    def removeOccurrences(self, s: str, part: str) -> str:
        stack = []
        part_length = len(part)

        for char in s:
            stack.append(char)

            if len(stack) >= part_length:
                if "".join(stack[-part_length:]) == part:
                    del stack[-part_length:]

        return "".join(stack)

The implementation uses a list as a stack because Python lists support efficient append and deletion from the end.

We first store the length of part to avoid recalculating it repeatedly.

For every character in s, we append it to the stack. After appending, we check whether the most recent characters form the substring part.

The expression:

stack[-part_length:]

extracts the suffix of the current stack. If it matches part, we remove those characters immediately using:

del stack[-part_length:]

At the end, we join all remaining characters into the final string.

This implementation directly follows the algorithm described earlier and efficiently maintains the partially processed result.

Go Solution

func removeOccurrences(s string, part string) string {
    stack := make([]byte, 0)
    partLen := len(part)

    for i := 0; i < len(s); i++ {
        stack = append(stack, s[i])

        if len(stack) >= partLen {
            match := true

            for j := 0; j < partLen; j++ {
                if stack[len(stack)-partLen+j] != part[j] {
                    match = false
                    break
                }
            }

            if match {
                stack = stack[:len(stack)-partLen]
            }
        }
    }

    return string(stack)
}

The Go implementation uses a []byte slice as the stack because strings in Go are immutable.

Appending characters is efficient with append, and removing the suffix is done using slice truncation:

stack = stack[:len(stack)-partLen]

Unlike Python, Go does not provide direct string slicing comparisons as conveniently, so we manually compare characters in a loop.

Since the problem only contains lowercase English letters, using bytes is completely safe and efficient.

Worked Examples

Example 1

s = "daabcbaabcbc"
part = "abc"

Step	Character	Stack After Append	Match Found	Stack After Removal
1	d	d	No	d
2	a	da	No	da
3	a	daa	No	daa
4	b	daab	No	daab
5	c	daabc	Yes	da
6	b	dab	No	dab
7	a	daba	No	daba
8	a	dabaa	No	dabaa
9	b	dabaab	No	dabaab
10	c	dabaabc	Yes	daba
11	b	dabab	No	dabab
12	c	dababc	Yes	dab

Final answer:

"dab"

Example 2

s = "axxxxyyyyb"
part = "xy"

Step	Character	Stack After Append	Match Found	Stack After Removal
1	a	a	No	a
2	x	ax	No	ax
3	x	axx	No	axx
4	x	axxx	No	axxx
5	x	axxxx	No	axxxx
6	y	axxxxy	Yes	axxx
7	y	axxxy	Yes	axx
8	y	axxy	Yes	ax
9	y	axy	Yes	a
10	b	ab	No	ab

Final answer:

"ab"

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n × m)	Each character may trigger a suffix comparison of length m
Space	O(n)	The stack may store the entire string

The stack grows at most to the size of the input string, so the space complexity is linear.

For every character added, we may compare up to m characters against part. Therefore the total worst case runtime is O(n × m).

Given the constraints of at most 1000 characters, this solution is easily efficient enough.

Test Cases

solution = Solution()

# Provided examples
assert solution.removeOccurrences("daabcbaabcbc", "abc") == "dab"  # multiple removals
assert solution.removeOccurrences("axxxxyyyyb", "xy") == "ab"  # cascading removals

# No occurrence
assert solution.removeOccurrences("hello", "xyz") == "hello"  # substring absent

# Entire string removed
assert solution.removeOccurrences("aaaa", "aa") == ""  # repeated full removals

# Single character part
assert solution.removeOccurrences("banana", "a") == "bnn"  # remove all matching chars

# Overlapping pattern behavior
assert solution.removeOccurrences("aaaaa", "aa") == "a"  # overlapping removals

# Pattern equals string
assert solution.removeOccurrences("abc", "abc") == ""  # exact full removal

# Pattern longer than string
assert solution.removeOccurrences("ab", "abcd") == "ab"  # impossible match

# Repeated boundary formation
assert solution.removeOccurrences("abababa", "aba") == "b"  # new matches form after removal

# Minimal input
assert solution.removeOccurrences("a", "a") == ""  # smallest valid input

# Single remaining character
assert solution.removeOccurrences("abcabcxabc", "abc") == "x"  # repeated removals around center

Test	Why
"daabcbaabcbc", "abc"	Validates repeated removals
"axxxxyyyyb", "xy"	Validates cascading adjacent removals
"hello", "xyz"	Confirms unchanged result when no match exists
"aaaa", "aa"	Confirms complete deletion
"banana", "a"	Tests single-character pattern
"aaaaa", "aa"	Tests overlapping behavior
"abc", "abc"	Tests full-string removal
"ab", "abcd"	Tests pattern longer than string
"abababa", "aba"	Tests new matches forming after removal
"a", "a"	Tests smallest constraints
"abcabcxabc", "abc"	Tests multiple separated removals

Edge Cases

One important edge case occurs when removing a substring creates a new occurrence across the boundary of the removed section. For example:

s = "abababa"
part = "aba"

After removing the first "aba", the remaining characters become adjacent and form another occurrence. A naive implementation that does not properly continue checking can miss this. The stack approach handles this naturally because every newly formed suffix is checked immediately.

Another tricky case is when part contains only one character. For example:

s = "banana"
part = "a"

Every occurrence must be removed independently. Some implementations incorrectly assume the substring length is greater than one. The stack method still works correctly because suffix checking with length 1 is valid.

A third important edge case is overlapping patterns such as:

s = "aaaaa"
part = "aa"

The occurrences overlap heavily. If removals are not processed carefully in left-to-right order, incorrect results may occur. The stack solution correctly removes the leftmost occurrence as soon as it forms, preserving the intended behavior defined by the problem statement.