Remove All Occurrences of a Substring Solution

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.

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.

Logic:

  • We make a copy of our string s (x in code) and then iterate over the string s.
  • Now in the current iteration if j is greater than or equal to m that means that we have seen at least m elements, so we can check whether the substring of last m characters is equal to part or not. If it is equal, we reduce the variable ‘j’ by m showing that we have removed this substring and now we will overwrite the characters from index j.
  • Finally we will return the substring of x of length j.

Program:

string removeOccurrences(string s, string part) {
	string x = s;
	int n = s.size(), m = part.size(), i, j;
	for (i = 0, j = 0; i < n; i++) {
		x[j++] = s[i];
		if (j >= m && x.substr(j - m, m) == part)
			j -= m;
	}
	return x.substr(0, j);
}

Weekly Contest 247

Biweekly Contest 55

June Long Challenge 2021 Solutions

March Long Challenge 2021 Solutions

April Long Challenge 2021 Solutions

Codechef Long Challenge Solutions

February Long Challenge 2021

January Long Challenge 2021

November Challenge 2020 SOLUTION CodeChef

October Lunchtime 2020 CodeChef SOLUTIONS

Related :

Related :

Leave a Comment