#1910

Medium

auto_awesomeStack-based state management

LeetCode Problem Workspace

Remove All Occurrences of a Substring

Remove all occurrences of a specified substring from a string using efficient stack-based state management.

Problem Statement

You are given two strings, s and part. Perform the following operation on s until no occurrences of part remain in s: remove every occurrence of part as a contiguous substring of s. Return the resulting string after all occurrences of part have been removed.

A substring is defined as a contiguous sequence of characters within a string. Note that removing one occurrence of the pattern may expose a new occurrence, so repeated applications of the operation may be necessary to fully remove all instances of part.

Examples

Example 1

Input: s = "daabcbaabcbc", part = "abc"

Output: "dab"

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"

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 <= 1000
1 <= part.length <= 1000
s and part consists of lowercase English letters.

Solution Approach

Stack-based Approach

This problem is best solved by using a stack to simulate the string state. Traverse the string s and push characters onto the stack. For each new character, check if the stack's top matches the pattern part. If it does, remove it by popping the stack, effectively eliminating an occurrence of part.

Efficient String Simulation

The stack simulates the string building process, which helps manage occurrences of part in an efficient manner. After each character is added to the stack, check if a substring match is found at the top of the stack. This approach minimizes unnecessary string copying or searching, ensuring optimal time complexity.

Handling New Occurrences

When part is removed from s, new instances of part might appear in the resulting string. Therefore, the stack must be carefully managed to ensure all occurrences are completely eliminated. The solution ensures that no pattern is left behind by simulating string updates with each removal.

Complexity Analysis

Metric	Value
Time	O(n + m)
Space	O(n + m)

The time complexity is O(n + m), where n is the length of string s and m is the length of part. The space complexity is O(n + m), due to the stack storing up to n characters and the temporary space used for matching part during the traversal of s.

What Interviewers Usually Probe

Look for candidates who use stack-based state management efficiently.
Evaluate if the candidate handles the repeated removal of part effectively.
Assess whether the candidate understands the complexities involved in removing part and handling potential new occurrences.

Common Pitfalls or Variants

Common pitfalls

Forgetting to check for new occurrences of part after each removal, leading to incorrect results.
Using inefficient string operations like string slicing or replacing, which could increase time complexity.
Overcomplicating the solution by failing to leverage the stack for optimal string state management.

Follow-up variants

What if part appears multiple times in a row? The candidate should ensure the solution can handle repeated consecutive occurrences of part efficiently.
What if part is not present in s at all? Ensure that the candidate can handle the case where no removals are needed.
What if part is equal to the entire string s? This should result in an empty string after the removal.

FAQ

What is the primary pattern used to solve the "Remove All Occurrences of a Substring" problem?

The primary pattern for solving this problem is stack-based state management, which allows for efficient removal of all occurrences of a substring in the string.

How do we handle the appearance of new occurrences of part in "Remove All Occurrences of a Substring"?

New occurrences of part can appear after a removal. The stack approach ensures that these new occurrences are identified and removed efficiently in subsequent steps.

What is the time complexity of the "Remove All Occurrences of a Substring" problem?

The time complexity is O(n + m), where n is the length of string s and m is the length of part.

Can the "Remove All Occurrences of a Substring" problem be solved without using a stack?

While it can be done using other methods like string slicing or regular expressions, the stack-based approach is the most efficient and optimal for this problem.

What are common mistakes when solving the "Remove All Occurrences of a Substring" problem?

Common mistakes include failing to check for new occurrences of part after removal, using inefficient string operations, and not leveraging the stack for optimal state management.

terminal

Solution

Solution 1

#### Python3

1

2

3

4

5

class Solution:
    def removeOccurrences(self, s: str, part: str) -> str:
        while part in s:
            s = s.replace(part, '', 1)
        return s

Continue Practicing

#2211 count collisions on a road #2296 design a text editor #2390 removing stars from a string