Skip to content

1910. Remove All Occurrences of a Substring

SourceBiweekly Contest 55 Q2DifficultyMediumRating1460

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.

Solutions

Solution 1: Brute Force

Thinking

Both \(s\) and \(\textit{part}\) are at most \(10^3\) long, so repeatedly locating and erasing one occurrence is acceptable.

Each step replaces the leftmost \(\textit{part}\). A later concatenation may recreate \(\textit{part}\), so the loop continues until none remain.

Every replacement shortens \(s\), so the process terminates and matches the required leftmost-first order.

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

1
2
3
4
5
6
7
8
class Solution {
    public String removeOccurrences(String s, String part) {
        while (s.contains(part)) {
            s = s.replaceFirst(part, "");
        }
        return s;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
class Solution {
public:
    string removeOccurrences(string s, string part) {
        int m = part.size();
        while (s.find(part) != -1) {
            s = s.erase(s.find(part), m);
        }
        return s;
    }
};

1
2
3
4
5
6
func removeOccurrences(s string, part string) string {
    for strings.Contains(s, part) {
        s = strings.Replace(s, part, "", 1)
    }
    return s
}

1
2
3
4
5
6
function removeOccurrences(s: string, part: string): string {
    while (s.includes(part)) {
        s = s.replace(part, '');
    }
    return s;
}

Solution 2: Stack

Thinking

Solution 1 rescans the whole string after every deletion. Each deletion shortens \(s\) by at least one character, so there can be \(O(n)\) rounds and the total time is \(O(n^2)\).

While reading left to right, any remaining occurrence of \(\textit{part}\) that is leftmost must end at the character just read. An earlier match would already have been removed.

Keep the surviving characters on a stack. After each push, pop the last \(m\) characters when they equal \(\textit{part}\). One pass performs every leftmost deletion.

Scan \(s\) from left to right and store the characters that have not been removed in a string \(st\). Append the current character. If \(st\) has length at least \(m = |\textit{part}|\) and its last \(m\) characters are \(\textit{part}\), delete those \(m\) characters. After the scan, \(st\) is the answer.

This matches Solution 1. At every moment \(st\) contains no occurrence of \(\textit{part}\), so the next match must end at the character just appended, which is the leftmost occurrence in what remains.

The time complexity is \(O(nm)\), and the space complexity is \(O(n)\), where \(n\) and \(m\) are the lengths of \(s\) and \(\textit{part}\).

1
2
3
4
5
6
7
8
9
class Solution:
    def removeOccurrences(self, s: str, part: str) -> str:
        m = len(part)
        st = []
        for c in s:
            st.append(c)
            if len(st) >= m and ''.join(st[-m:]) == part:
                del st[-m:]
        return ''.join(st)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
class Solution {
    public String removeOccurrences(String s, String part) {
        int m = part.length();
        StringBuilder st = new StringBuilder();
        for (int i = 0; i < s.length(); ++i) {
            st.append(s.charAt(i));
            if (st.length() >= m && st.substring(st.length() - m).equals(part)) {
                st.setLength(st.length() - m);
            }
        }
        return st.toString();
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
class Solution {
public:
    string removeOccurrences(string s, string part) {
        int m = part.size();
        string st;
        for (char c : s) {
            st.push_back(c);
            if ((int) st.size() >= m && st.compare(st.size() - m, m, part) == 0) {
                st.erase(st.size() - m);
            }
        }
        return st;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
func removeOccurrences(s string, part string) string {
    m := len(part)
    st := make([]byte, 0, len(s))
    for i := 0; i < len(s); i++ {
        st = append(st, s[i])
        if len(st) >= m && string(st[len(st)-m:]) == part {
            st = st[:len(st)-m]
        }
    }
    return string(st)
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
function removeOccurrences(s: string, part: string): string {
    const m = part.length;
    const st: string[] = [];
    for (const c of s) {
        st.push(c);
        if (st.length >= m && st.slice(-m).join('') === part) {
            st.length -= m;
        }
    }
    return st.join('');
}

Comments