Today’s problem

https://leetcode.com/problems/remove-all-occurrences-of-a-substring/description/

Intuition

In this case, we need to delete all the occurance of “part” in “s”. Therefore, we can check whether “s” contains “part”. Then we can delete it from the string.

Approach

Method 1. You can use a stack to do that. When you detect that your stack input a string that is the same to “part”, then we can delete the string from the stack.

Method 2. You can use the python function to find and delete “part” from the original string S.

Complexity

  • Time complexity: $O(N\times M)$, N is the length of s, M is the length of part.

  • Space complexity: $O(1)$

Code

class Solution:
    def removeOccurrences(self, s: str, part: str) -> str:
        st = []
        N = len(part)
        for ch in s:
            st.append(ch)
            if len(st) >= N:
                flag = True
                for i in range(1, N + 1):
                    if st[-i] != part[-i]:
                        print(st[-i], part[-i])
                        flag = False
                        break
                
                if flag:
                    for i in range(N):
                        st.pop()
    
        return ''.join(st)

Real Python

class Solution:
    def removeOccurrences(self, s: str, part: str) -> str:
        while part in s:
            s = s.replace(part,"",1)
        return s