Solution For Remove All Occurrences Of A Substring

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).

Step by Step Implementation For Remove All Occurrences Of A Substring

public class Solution {
    public String removeSubstring(String s, String t) {
        // edge case
        if (t.length() == 0) {
            return s;
        }
        
        StringBuilder sb = new StringBuilder();
        
        for (int i = 0; i < s.length(); i++) {
            // if the current character is not part of the substring to remove
            if (t.indexOf(s.charAt(i)) == -1) {
                sb.append(s.charAt(i));
            }
        }
        
        return sb.toString();
    }
}

def remove_all_occurrences_of_a_substring(string, substring):

# Base case
if len(substring) == 0:
return string

# Recursive case
if string.find(substring) != -1:
return remove_all_occurrences_of_a_substring(string.replace(substring, ""), substring)

return string

Given a string s and a string t, remove all occurrences of t from s.

function removeAllOccurrencesOfSubstring(s, t) {
    // your code goes here
}

class Solution {
public:
    string removeAllOccurrencesOfA(string s, string a) {
        // Your code here
    }
};

public class Solution {
    public string RemoveAllOccurrencesOfASubstring(string s, string t) {
        // Edge case
        if (s == null || t == null) {
            return s;
        }
        
        // Variable to store the final string
        StringBuilder sb = new StringBuilder();
        
        // Iterate through the string
        for (int i = 0; i < s.Length; i++) {
            // If the current character is not part of the substring to be removed
            if (i + t.Length <= s.Length && !s.Substring(i, t.Length).Equals(t)) {
                // Append it to the final string
                sb.Append(s[i]);
            } 
            // Otherwise, increment the index by the length of the substring (to skip over it)
            else {
                i += t.Length - 1;
            }
        }
        
        return sb.ToString();
    }
}