Description

Given a string S of lowercase letters, a duplicate removal consists of choosing two adjacent and equal letters, and removing them.

We repeatedly make duplicate removals on S until we no longer can.

Return the final string after all such duplicate removals have been made. It is guaranteed the answer is unique.
字符消消乐

Solution

Time Complexity O(N), 遍历，如果有要消除的，就退回到前一个进行消除

class Solution:
    def removeDuplicates(self, S: str) -> str:
        end = len(S)
        S=list(S)
        if set(S) == 1:
            return S[0] * (len(S)%2)
        start = 0
        i=0
        
        while (i<len(S)-1):
            if S[i]==S[i+1]:
                del S[i:i+2]
                i-=1 # check prev node
                i=max(0,i)
            else:
                i+=1
       
        return ''.join(S)