Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/1910.html

1910. Remove All Occurrences of a Substring

Level

Medium

Description

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.

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

Solution

Use indexOf to find the index of the occurrence of part in s, and remove the corresponding substring from s. Repeat this step until s does not contain part. Finally, return s`.

  • class Solution {
    public String removeOccurrences(String s, String part) {
        int partLength = part.length();
        while (s.indexOf(part) >= 0) {
            int index = s.indexOf(part);
            s = s.substring(0, index) + s.substring(index + partLength);
        }
        return s;
    }
}

  • // OJ: https://leetcode.com/problems/remove-all-occurrences-of-a-substring/
// Time: O()
// Space: O()
class Solution {
public:
    string removeOccurrences(string s, string t) {
        auto f = s.find(t);
        while (f != string::npos) {
            s.erase(f, t.size());
            f = s.find(t);
        }
        return s;
    }
};

  • # 1910. Remove All Occurrences of a Substring
# https://leetcode.com/problems/remove-all-occurrences-of-a-substring

class Solution:
    def removeOccurrences(self, s: str, part: str) -> str:
        stack = []
        pn = len(part)
        
        for c in s:
            stack.append(c)
            
            if len(stack) >= pn and "".join(stack[-pn:]) == part:
                for _ in range(pn):
                    stack.pop()

        return "".join(stack)

All Problems

All Solutions