Problem statement

https://leetcode.com/problems/remove-all-adjacent-duplicates-in-string/

Solution

It is given in the statement of the problem that no matter in which order we remove adjacent duplicates in our string, result will always be the same. It is not obvious for my why (that is why problem marked as easy, because we can use it), so we we choose the most convinient way for us. Let us go from left to right and try to add element by element. If we see that we have repetition when we add new element, it means that we have adjacent duplicate and we pop element. In the opposite case we add element to stack. In the end we just return what we have in our stack.

Complexity

Time and space complexity is O(n).

Code

class Solution:
    def removeDuplicates(self, s):
        stack = []
        for symb in s:
            if stack and stack[-1] == symb:
                stack.pop()
            else:
                stack.append(symb)
        return "".join(stack)