1910. Remove All Occurrences of a Substring

Mastering String Manipulation: Removing Occurrences with Efficiency

Thoughts and Talk

String manipulation tasks are ubiquitous in programming, and they often involve intricate logic and edge cases. The problem we're tackling today revolves around removing specific occurrences of a substring from a given string, but with a twist: we need to remove not only the substring but also the characters to its right until the next occurrence of the last character of the substring.

This problem might seem deceptively simple at first glance, but it demands a careful approach and a deep understanding of data structures and algorithms. By exploring various solutions, we can appreciate the nuances of problem-solving and the importance of optimizing our code for efficiency.

Problem Statement

Given a string s and a substring part, we need to remove all occurrences of part from s. However, the catch is that when we encounter an occurrence of part, we should remove not only part itself but also all the characters to its right until the next occurrence of the last character of part. If there is no such occurrence, we remove all characters to the right of part.

Approaches Explored

Approach 1: Brute Force

Pros:

Simple and easy to understand
No complex data structures or algorithms required

Cons:

Inefficient, especially for large strings and frequent occurrences of the substring
Time complexity: O(n * m), where n is the length of the string and m is the length of the substring

Approach 2: Stack-based Solution

Pros:

Efficient and optimized solution
Time complexity: O(n), where n is the length of the string

Cons:

Slightly more complex implementation compared to the brute force approach
Requires additional space for the stack data structure

Finalized Approach

After evaluating the pros and cons of both approaches, we opted for the stack-based solution as it provides better time complexity and efficiency, especially for larger inputs. This approach leverages the power of a stack data structure to maintain the characters that need to be preserved while removing the occurrences of part and the characters to its right until the next occurrence of the last character of part.

Executable Code

TheTechCruise.com Pyodide Terminal

class Solution:
    def removeOccurrences(self, s: str, part: str) -> str:
        st = []  # Initialize an empty stack

        # Helper function to get a slice of a list or string
        def get_part(m, n):
            return m[-n+1:] if len(m) >= n else m

        lp = len(part)

        # Special case: If the length of 'part' is 1, we can use string replacement
        if lp == 1:
            return s.replace(part, "")

        for i in range(len(s)):
            # If the stack contains enough characters to potentially form 'part'
            if len(st) + 1 >= lp and s[i] == part[-1]:
                # Check if the characters in the stack, combined with the current character,
                # form 'part'
                if get_part(st, lp) + [s[i]] == list(part):
                    # Pop the characters from the stack that form 'part'
                    for i in range(lp-1):
                        st.pop()
                else:
                    st.append(s[i])
            else:
                st.append(s[i])

        return "".join(st)  # Convert the stack back to a string and return it

sol = Solution()
# Test Case 1
print("Test Case 1:", sol.removeOccurrences("daabcbaabcbc", "abc"))  # "dab"

# Test Case 2
print("Test Case 2:", sol.removeOccurrences("axxxxyyyyb", "xy"))     # "axxxb"

# Test Case 3
print("Test Case 3:", sol.removeOccurrences("aabccbac", "abc"))      # "bac"

# Test Case 4
print("Test Case 4:", sol.removeOccurrences("aabbaabb", "ab"))       # ""

# Test Case 5
print("Test Case 5:", sol.removeOccurrences("xyz", "abc"))           # "xyz"

Code Analysis and Code Walk-through

Let's break down the code and understand how it works:

We start by initializing an empty stack st.

We define a helper function get_part that takes a list or string m and an integer n. It returns a slice of m starting from the last n characters. This function is used to check if the characters in the stack, combined with the current character, form part.

We store the length of the substring part in the variable lp.

If the length of part is 1, we can simply use the built-in replace method to remove all occurrences of part from s. This is a special case optimization.

We iterate over each character s[i] in the string s:

If the length of the stack st plus 1 is greater than or equal to the length of part (lp), and the current character s[i] matches the last character of part, we check if the characters in the stack, combined with the current character, form part.

If they form part, we pop lp-1 characters from the stack, effectively removing the occurrence of part and the characters to its right until the next occurrence of the last character of part.

If they don't form part, we push the current character s[i] onto the stack.

If the length of the stack plus 1 is less than the length of part, we simply push the current character s[i] onto the stack.

After iterating over the entire string, the stack will contain the modified string with the desired occurrences of part removed.

Finally, we convert the stack back to a string using the join method and return it as the result.

Example with Explanation

Let's consider an example to better understand the code's execution:

TheTechCruise.com Pyodide Terminal

s = "daabcbaabcbc"
part = "abc"

Here's a step-by-step explanation of how the code works:

The stack st is initialized as an empty list: [].

The length of part is lp = 3.

The string s is iterated over character by character:

'd' is pushed onto the stack: ['d']

'a' is pushed onto the stack: ['d', 'a']

'a' is pushed onto the stack: ['d', 'a', 'a']

'b' is pushed onto the stack: ['d', 'a', 'a', 'b']

'c' matches the last character of part, and the stack contains ['a', 'a', 'b'] which, combined with 'c', forms part. So, we pop 'b', 'a', and 'a' from the stack, leaving ['d'].

'b' is pushed onto the stack: ['d', 'b']

'a' is pushed onto the stack: ['d', 'b', 'a']

'a' is pushed onto the stack: ['d', 'b', 'a', 'a']

'b' is pushed onto the stack: ['d', 'b', 'a', 'a', 'b']

'c' matches the last character of part, and the stack contains ['a', 'a', 'b'] which, combined with 'c', forms part. So, we pop 'b', 'a', and 'a' from the stack, leaving ['d', 'b'].

'b' is pushed onto the stack: ['d', 'b', 'b']

'c' is pushed onto the stack: ['d', 'b', 'b', 'c']

After iterating over the entire string, the stack contains ['d', 'a', 'b'].

The stack is converted back to a string "dab" and returned as the result.

Discussion on Complexity

The time complexity of this solution is O(n), where n is the length of the input string s. This is because we iterate over the string once, performing constant-time operations (stack push and pop) for each character.

The space complexity is O(n) in the worst case, where the entire input string needs to be stored in the stack. However, in practice, the space complexity is often much smaller, as we pop characters from the stack when we encounter occurrences of part.

Conclusion

In this blog post, we explored a problem involving string manipulation and the removal of specific occurrences of a substring, along with the characters to its right until the next occurrence of the last