Remove All Occurrences of a Substring

Problem

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 part and remove it from s.

Return s after removing all occurrences of part.

A substring is a contiguous sequence of characters in a string.

Examples

Example 1:

Input: s = "daabcbaabcbc", part = "abc"
Output: "dab"
**Explanation** : The following operations are done:
- s = "da** _abc_** baabcbc", remove "abc" starting at index 2, so s = "dabaabcbc".
- s = "daba** _abc_** bc", remove "abc" starting at index 4, so s = "dababc".
- s = "dab** _abc_** ", 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 = "axxx** _xy_** yyyb", remove "xy" starting at index 4 so s = "axxxyyyb".
- s = "axx** _xy_** yyb", remove "xy" starting at index 3 so s = "axxyyb".
- s = "ax** _xy_** yb", remove "xy" starting at index 2 so s = "axyb".
- s = "a** _xy_** b", 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

Video explanation

Here is the video explaining below methods in detail. Please check it out:

<div class="youtube-embed"><iframe src="https://www.youtube.com/embed/Ywv7YBNqEJw" frameborder="0" allowfullscreen></iframe></div>

Method 1 - Naive

This approach continues to remove the substring part from the string s until no more occurrences are found. It uses the contains method to check for the presence of part and the indexOf method to find its position. The substring method is used to rebuild the string without the part.

Code

Java

class Solution {
    public String removeOccurrences(String s, String part) {
        int idx;
        while ((idx = s.indexOf(part)) != -1) {
            s = s.substring(0, idx) + s.substring(idx + part.length());
        }
        
        return s;
    }
}

Python

class Solution:
    def removeOccurrences(self, s: str, part: str) -> str:
        while part in s:
            idx = s.find(part)
            s = s[:idx] + s[idx + len(part):]
        
        return s

Complexity

• ⏰ Time complexity: O((n/m) * n), where n is the length of the string s and m is the length of the substring part. In the worst case, each removal might take up to O(n) time, and we might have to do this n/m times.
• 🧺 Space complexity: O(n) due to the creation of new strings during each iteration.

Method 2 - Naive - Delete chars in mutable string

To solve this problem, we can use a simple iterative approach:

1. We will keep looking for the part in string s.
2. As long as the part is found, we will remove it by reconstructing the string.
3. Once no more occurrences of part are found, we return the modified string.

This approach leverages the built-in string functions efficiently to find and modify the string iteratively.

Code

Java

We use a StringBuilder to facilitate efficient modifications. The indexOf method helps find the leftmost occurrence of part, and the delete method removes it.

class Solution {
    public String removeOccurrences(String s, String part) {
        StringBuilder ans = new StringBuilder(s);
        
        int idx;
        while ((idx = ans.indexOf(part)) != -1) {
            ans.delete(idx, idx + part.length());
        }
        
        return ans.toString();
    }
}

Python

class Solution:
    def removeOccurrences(self, s: str, part: str) -> str:
        ans = list(s)
        m = len(part)
        
        i = 0
        while i <= len(ans) - m:
            if "".join(ans[i:i + m]) == part:
                ans = ans[:i] + s_list[i + part_len:]
                i = max(0, i - m)  # Reset index to check for overlapping parts
            else:
                i += 1
        
        return "".join(ans)

Complexity

• ⏰ Time complexity: O(n ^ 2 / m). In the worst case, this might need to iterate through the length of the string s multiple times.
• 🧺 Space complexity: O(1) additional space, but O(n) if we consider the space for the result string.

Method 3 - Using Stack

Here is the approach:

1. Traverse the string from the beginning, pushing each character onto a stack until its size matches that of part.
2. When the stack's size equals part, check characters from the end of part against the top of the stack. If they match, pop the stack for each matching character.
3. If a character in part does not match the top of the stack, refill the stack with the previously checked characters and continue.
4. After processing, build the final string using the remaining characters in the stack by converting them with StringBuilder or equivalent.

Code

Java

class Solution {
    public String removeOccurrences(String s, String part) {
        Stack<Character> stack = new Stack<>();
        int m = part.length();
        
        for (char ch : s.toCharArray()) {
            stack.push(ch);
            if (stack.size() >= m) {
                StringBuilder temp = new StringBuilder();
                boolean isMatch = true;
                for (int i = m - 1; i >= 0; i--) {
                    if (stack.isEmpty() || stack.peek() != part.charAt(i)) {
                        isMatch = false;
                        break;
                    }
                    temp.append(stack.pop());
                }
                if (!isMatch) {
                    for (int i = temp.length() - 1; i >= 0; i--) {
                        stack.push(temp.charAt(i));
                    }
                }
            }
        }
        
        StringBuilder ans = new StringBuilder();
        while (!stack.isEmpty()) {
            ans.append(stack.pop());
        }
        
        return ans.reverse().toString();
    }
}

Python

class Solution:
    def removeOccurrences(self, s: str, part: str) -> str:
        stack: list[str] = []
        m: int = len(part)
        
        for ch in s:
            stack.append(ch)
            if len(stack) >= m:
                temp = []
                is_match = True
                for j in range(m - 1, -1, -1):
                    if not stack or stack[-1] != part[j]:
                        is_match = False
                        break
                    temp.append(stack.pop())
                
                if not is_match:
                    stack.extend(reversed(temp))

        return ''.join(stack)

Complexity

• ⏰ Time complexity: O(n.m), because for each character in s, checking the top m characters of the stack for a match takes O(m) time.
• 🧺 Space complexity: O(n + m), because the stack uses O(n) space, and temporary matching substring use O(m) space.

Method 4 - Using Stack String

The idea is to use a stack to build the resulting string while checking for the part substring on the fly.

1. Initialise an empty list to use as a stack.
2. Iterate through the string s, pushing each character onto the stack.
3. Each time you push a character, check if the top of the stack forms the part string.
4. If it does, pop part.length characters from the stack to remove the part substring.
5. After processing all characters, join the stack to form the resulting string.

Code

Java

class Solution {
    public String removeOccurrences(String s, String part) {
        StringBuilder stack = new StringBuilder();
        int m = part.length();
        
        for (char c : s.toCharArray()) {
            stack.append(c);

			int len = stack.length();
            if (len >= m && 
                stack.substring(len - m).equals(part)) {
                stack.delete(len - m, len);
            }
        }
        
        return stack.toString();
    }
}

Python

class Solution:
    def removeOccurrences(self, s: str, part: str) -> str:
        stack: list[str] = []
        m: int = len(part)
        
        for ch in s:
            stack.append(ch)
            if len(stack) >= m and ''.join(stack[-m:]) == part:
                del stack[-m:]
        
        return ''.join(stack)

Complexity

• ⏰ Time complexity: O(n.m), where n is the length of the string s. Each character is processed once.
• 🧺 Space complexity: O(n), as we might need to store all characters in the stack.