Skip to content

1910. Remove All Occurrences of a Substring 👍

  • Time: $O(nk)$
  • Space: $O(n)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
class Solution {
 public:
  string removeOccurrences(string s, string part) {
    const int n = s.length();
    const int k = part.length();

    string t(n, ' ');
    int j = 0;  // t's index

    for (int i = 0; i < n; ++i) {
      t[j++] = s[i];
      if (j >= k && t.substr(j - k, k) == part)
        j -= k;
    }

    return t.substr(0, j);
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
class Solution {
  public String removeOccurrences(String s, String part) {
    final int n = s.length();
    final int k = part.length();

    StringBuilder sb = new StringBuilder(s);
    int j = 0; // sb's index

    for (int i = 0; i < n; ++i) {
      sb.setCharAt(j++, s.charAt(i));
      if (j >= k && sb.substring(j - k, j).toString().equals(part))
        j -= k;
    }

    return sb.substring(0, j).toString();
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
class Solution:
  def removeOccurrences(self, s: str, part: str) -> str:
    n = len(s)
    k = len(part)

    t = [' '] * n
    j = 0  # t's index

    for i, c in enumerate(s):
      t[j] = c
      j += 1
      if j >= k and ''.join(t[j - k:j]) == part:
        j -= k

    return ''.join(t[:j])