We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Remove All Occurrences of a Substring

Number: 2021

Difficulty: Medium

Paid? No

Companies: Microsoft, IBM, Bloomberg, Amazon, Goldman Sachs, Google, Arista Networks, X, Zoho

Problem Description

Given two strings s and part, repeatedly remove the leftmost occurrence of part from s until s no longer contains part. Return the resulting string s after all occurrences of part have been removed.

Key Insights

  • Use a stack-like approach to process the string while checking for the substring part.
  • Append each character from s to a result container and compare the recent characters with part.
  • When the end of the container matches part, remove that segment immediately.
  • This efficient simulation avoids repeatedly scanning the string.

Space and Time Complexity

Time Complexity: O(n * m) in the worst-case, where n is the length of s and m is the length of part. Space Complexity: O(n) for storing the resultant characters in the stack.

Solution

We use a stack-like approach to build the answer character by character. For each character in s, we append it to a result container (acting as a stack). After every addition, we check if the suffix of the container forms the substring part. If it does, we remove those characters from the container. This simulates the removal process efficiently without searching through the entire string repeatedly. The primary data structure used is a list (or equivalent in other languages) serving as a stack.

Code Solutions

# Define the function to remove all occurrences of a substring
def remove_occurrences(s: str, part: str) -> str:
    # Initialize an empty list to serve as a stack for characters
    stack = []
    part_length = len(part)
    
    # Iterate over each character in the string s
    for char in s:
        # Append the current character to the stack
        stack.append(char)
        # If the stack end is at least as long as part, and it matches part, pop part_length characters
        if len(stack) >= part_length and "".join(stack[-part_length:]) == part:
            # Remove the last part_length characters from the stack
            del stack[-part_length:]
            
    # Join the characters to form the resulting string
    return "".join(stack)

# Example usage:
s = "daabcbaabcbc"
part = "abc"
print(remove_occurrences(s, part))  # Output: "dab"
← Back to All Questions