LeetCode 1047: Remove All Adjacent Duplicates In String

Stack

We can consider an adjacent duplicate pair like “aa” or “cc” as “()”. Removal of such a pair may produce more duplicate pairs only if there is nesting like: “(())”. For example: “zaaz” or “poop”. So, we use a stack to remove the nested duplicate pairs.

Time: $\mathcal{O}(n)$ , space: same.

class Solution:
    def removeDuplicates(self, s: str) -> str:
        stack = []
        for c in s:
            if stack and stack[-1] == c:
                stack.pop()
            else:
                stack.append(c)

        return "".join(stack)

Two pointers

If in-place modification of str was available, like this problem, we could use two pointers to consolidate the answer in s[0 : i+1] and perhaps return the len (= i+1) to the caller of the function. In that way, we would need constant extra space.

Time: $\mathcal{O}(n)$ , space: $\mathcal{O}(1)$ .

class Solution:
    def is_duplicate(self, i, j, s) -> bool:
        if i < 0:
            return False
        return s[i] == s[j]

    def removeDuplicates(self, s: str) -> str:
        s = list(s)
        i = -1
        for j in range(len(s)):
            if self.is_duplicate(i, j, s):
                i -= 1
            else:
                i += 1
                s[i] = s[j]
        
        return "".join( s[:i+1] )

unreasonably effective