1910. Remove All Occurrences of a Substring LeetCode Solution
In this guide, you will get 1910. Remove All Occurrences of a Substring LeetCode Solution with the best time and space complexity. The solution to Remove All Occurrences of a Substring problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Problem Statement of Remove All Occurrences of a Substring
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”.
1 <= s.length <= 1000
1 <= part.length <= 1000
s and part consists of lowercase English letters.
Complexity Analysis
Time Complexity: O(nk)
Space Complexity: O(n)
1910. Remove All Occurrences of a Substring LeetCode Solution in C++
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);
}
}; /* code provided by PROGIEZ */
1910. Remove All Occurrences of a Substring LeetCode Solution in Java
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();
}
} // code provided by PROGIEZ
1910. Remove All Occurrences of a Substring LeetCode Solution in Python
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]) # code by PROGIEZ
