Remove All Occurrences Of A Substring - Leetcode Solution

Problem Statement:

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 conducted: - s = "daabcbaabcbc", remove "abc" -> "dabaabcbc" - s = "dabaabcbc", remove "abc" -> "dababcbc" - s = "dababcbc", remove "abc" -> "dabcbc" - s = "dabcbc", remove "abc" -> "dab" Now s has no occurrences of "abc".

Example 2:

Input: s = "axxxxyyyyb", part = "xy" Output: "ab" Explanation: The following operations are conducted: - s = "axxxxyyyyb", remove "xy" -> "axxxxyyyb" - s = "axxxxyyyb", remove "xy" -> "axxxyyyb" - s = "axxxyyyb", remove "xy" -> "axyyyb" - s = "axyyyb", remove "xy" -> "ab" Now s has no occurrences of "xy".

Solution:

We can solve this problem using string manipulations. We can keep removing all occurrences of the given substring from the input string until there are no more occurrences of the substring left.

One way of doing this is to keep finding the leftmost occurrence of the substring and remove it from s using string slicing and concatenation. We can repeat this process until there are no more occurrences of part left in s.

Algorithm:

1. Initialize a variable pointer as 0.
2. Repeat the following steps until there are no more occurrences of part left in s: a. Find the index of the leftmost occurrence of part in s starting from pointer. b. If there are no more occurrences of part left in s, break the loop. c. Otherwise, remove the leftmost occurrence of part from s using string slicing and concatenation. d. Update pointer as the index of the character that comes immediately after the removed section of s.
3. Return s.

Python Code:

def removeOccurrences(s: str, part: str) -> str: pointer = 0 while True: index = s.find(part, pointer) if index == -1: break s = s[:index] + s[index+len(part):] pointer = index return s

Time Complexity: O(n^2) (worst case) where n is the length of the input string s.

Space Complexity: O(n) where n is the length of the input string s (worst case, when there are no occurrences of part in s).

1