Remove All Adjacent Duplicates In String — LeetCode 1047 Python Solution

The problem

You are given a string s consisting of lowercase English letters. A duplicate removal consists of choosing two adjacent and equal letters and removing them.

Example

Input

s = "abbaca"

Output

"ca"

Explanation

For example, in "abbaca" we could remove "bb" since the letters are adjacent and equal, and this is the only possible move. The result of this move is that the string is "aaca", of which only "aa" is possible, so the final string is "ca".

Python solution

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

Complexity

Pattern: Stack

When the most recent unresolved thing is the one that matters, use a stack. LeetCode 1047. Remove All Adjacent Duplicates In String is filed here on both counts: the reference solution below belongs to the algorithm family this hub collects, and LeetCode tags it Stack.

The stack guide has the Python template for the pattern and the 194 LeetCode problems that use it.

Related problems