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.
 
Example 1:
Input: "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".

 
Note:

1 <= S.length <= 20000
S consists only of English lowercase letters.

Difficulty: introductory

Starter code:

class Solution:
    def removeDuplicates(self, S: str) -> str:
        

Solutions:
from string import ascii_lowercase
class Solution:
    def removeDuplicates(self, S: str) -> str:
        
        dup = {2*ch for ch in ascii_lowercase}
        
        prev_length = -1
        
        while prev_length!=len(S):
            prev_length = len(S)
            for d in dup:
                S = S.replace(d,'')
        
        return S

class Solution:
    def removeDuplicates(self, S: str) -> str:
        
        list1 = []
        for i in S:
            if len(list1) > 0:
                if list1[-1] != i:
                    list1.append(i)
                else:
                    list1 = list1[:-1]
            else:
                list1.append(i)
            
        result = ''
        for i in list1:
            result += i
            
        return result

class Solution:
    def removeDuplicates(self, S: str) -> str:
        
        stack = []
        
        for char in S:
            
            if char not in stack or char != stack[-1]:
                stack += [char]
            
            else:
                stack = stack[: -1]
            #print(stack)
            
        return ''.join(stack)


class Solution:
    def removeDuplicates(self, S: str) -> str:
        str_2_arr = list(S)
        while True:
            tmp_arr = []
            i = 0
            while i < len(str_2_arr):
                if i < len(str_2_arr)-1 and str_2_arr[i] == str_2_arr[i+1]:
                    i += 2
                    continue
                    
                tmp_arr.append(str_2_arr[i])
                i += 1
  
            if str(tmp_arr) == str(str_2_arr):
                break
              
            str_2_arr =  list(tmp_arr)  
            tmp_arr = []
            
        return ''.join(str_2_arr)
            
            
            


class Solution:
    def removeDuplicates(self, S: str) -> str:
        
        if len(S) == 1:
            return S
        
        stack = []
        
        for i in range(len(S)):
            if len(stack) > 0 and stack[-1] == S[i]:
                stack.pop()
            else:
                stack.append(S[i])
        
        return ''.join(stack)

class Solution:
    def removeDuplicates(self, S: str) -> str:
            
    
        stack = []
        for i in S:
            
            if len(stack) == 0:
                stack.append(i)
                
            elif i == stack[-1]:
                stack.pop()
                
            else:
                stack.append(i)
                
                
        return ''.join(stack)

class Solution:
    def removeDuplicates(self, S: str) -> str:
        i = 0
        while i < len(S) -1:
            if S[i] != S[i+1]:
                i += 1
                continue
            else:
                S = S[0:i] + S[i+2:]
                if i > 0:
                    i -= 1
                #print(S)
        return S
            


class Solution:
    def removeDuplicates(self, S: str) -> str:
        stack = S[0]
        for i in range(1,len(S)):
            if len(stack) == 0:
                stack += S[i]
            elif stack and stack[-1] != S[i]:
                stack += S[i]
            elif stack:
                stack = stack[:-1]
        
        return stack

class Solution:
    def removeDuplicates(self, S: str) -> str:
        i = 0
        while(i != len(S)-1 and len(S) > 1):
            if(S[i] == S[i+1]):
                S = S[:i] + S[i+2:]
                i = 0 if(not i) else i-1
            else:
                i += 1
        return S
                
            


class Solution:
    def removeDuplicates(self, string: str) -> str:
        stack=deque()
        stack.append(string[0])
        index=0
        for i in range(1,len(string)):
            stack.append(string[i])
            index+=1
            if stack[index]==stack[index-1] and len(stack)>1:
                for i in range(2):
                    if stack:
                        stack.pop()
                        index-=1
        s=''
        for i in range(len(stack)):
            s+=stack[i]
        return (s)


class Solution:
    def removeDuplicates(self, S: str) -> str:
        def delete(S,index):
            S = S[:index]+S[index+1:]
            return S
    
        stack = []
        stack_top = -1
        pointer = 0
        while pointer < len(S):
            if len(stack) == 0 or S[pointer] != stack[stack_top]:
                stack.append(S[pointer])
                pointer+=1
                stack_top+=1
            else:
                S = delete(S,pointer-1)
                pointer-=1
                S = delete(S,pointer)
                stack.pop(-1)
                stack_top-=1
        return S

class Solution:
    def removeDuplicates(self, S: str) -> str:
        def delete(S,index):
            S = S[:index]+S[index+1:]
            return S
    
        stack = []
        stack_top = len(stack)-1
        pointer = 0
        while pointer < len(S):
            if len(stack) == 0 or S[pointer] != stack[stack_top]:
                stack.append(S[pointer])
                pointer+=1
                stack_top+=1
            else:
                S = delete(S,pointer-1)
                pointer-=1
                S = delete(S,pointer)
                stack.pop(-1)
                stack_top-=1
        return S

class Solution:
    def removeDuplicates(self, S: str) -> str:
        # use a stack to save char, cnt
        if not S:
            return None
        stack = []
        for s in S:
            if len(stack) > 0 and s == stack[-1][0]:
                stack[-1][1] += 1
            else:
                stack.append([s, 1])
            if stack[-1][1] == 2:
                stack.pop()
        return ''.join(char * num for char, num in stack)


class Solution:
    def removeDuplicates(self, S: str) -> str:
        ## stack application
        stack = []
        for i in S:
            if not stack:
                stack.append(i)
            elif i == stack[-1]:
                stack.pop()
            else:
                stack.append(i)
        
        return ''.join(stack)

class Solution:
    def removeDuplicates(self, S: str) -> str:
        temp = len(S)-1
        temp1 = len(S)-1
        while True:
            temp1 = temp
            if len(S)>=2:
                i = 0
                while i<temp:
                    if S[i] == S[i+1]:
                        S = S[:i] + S[i+2:]
                        temp -= 2
                    i+=1
            if temp == temp1:
                return S

class Solution:
    def removeDuplicates(self, S: str) -> str:
        # преобразовываем строку в список
        str_list = []
        for i in range(len(S)):
            str_list.append(S[i])
        
        # убираем дубли
        i = 0
        while i < len(str_list)-1:
            if str_list[i] == str_list[i+1]:
                del(str_list[i])
                del(str_list[i])
                if i > 0: i -= 1
            else:
                i += 1
        
        # преобразовываем обратно в строку
        str_end = ''
        for i in range(len(str_list)):
            str_end += str(str_list[i])
        return str_end


class Solution:
    def removeDuplicates(self, s: str) -> str:
        stack = [0]
        for i in range(len(s)):
            if s[i] == stack[-1]:
                stack.pop()
                continue
            if s[i] != stack[-1]:
                stack.append(s[i])
                
        res = ''
        for i in range(1, len(stack)):
            res+= stack[i]
            
        return res

class Solution:
    def removeDuplicates(self, s: str) -> str:
        i = 0
        while i+1<len(s):
            if s[i] == s[i+1]:
                s = s[:i]+s[i+2:]
                if i>=1:
                    i-=1
            else:
                i+=1
        return s

class Solution:
    def removeDuplicates(self, S: str) -> str:
        if len(S) <= 1:
            return S
        stack = []
        stack.append(S[0])
        
        index = 1
        while index < len(S):
            stack.append(S[index])
            # print(stack)
            index += 1
            
            self.popDups(stack)
        
        s = ''
        for c in stack:
            s += c
        
        return s
    
    def popDups(self, stack):
        
        to_pop = True
        while stack and to_pop:
            this_item = stack.pop()
            if len(stack) != 0:
                next_item = stack[-1]
                if this_item == next_item:
                    stack.pop()
                else:
                    stack.append(this_item)
                    to_pop = False
            else:
                stack.append(this_item)
                to_pop = False
        
        
        
        
        
        # to_pop = True
        # while to_pop and stack:
        #     item = stack.pop()
        #     if not stack:
        #         stack.append(item)
        #         to_pop = False
        #     else:
        #         next_item = stack.pop()
        #         if item != next_item:
        #             stack.append(next_item)
        #             stack.append(item)
        #             to_pop = False                    
        
        
                
                


class Solution:
    def removeDuplicates(self, s: str) -> str:
        i = 0
        while i<len(s)-1:
            if s[i] == s[i+1]:
                s = s[:i]+s[i+2:]
                if i > 0: 
                    i-=1
            else:
                i+=1
        return s

class Solution:
    def removeDuplicates(self, S: str) -> str:
        while True:
            counter = 0
            
            i = 1
            remove_list = []
            while i < len(S):
                if S[i] == S[i-1]:
                    counter = 1
                    remove_list.append(i)
                    i += 1
                i += 1
            for j in range(len(remove_list), 0, -1):
                idx = remove_list[j-1]
                if idx == len(S)-1:
                    S = S[:idx-1]
                else:
                    S = S[:idx-1] + S[idx+1:]
            if counter == 0: break
        return S

class Solution:
    def removeDuplicates(self, S: str) -> str:
        
        remove_ls = []
        start = True
        tmp = S
        while start or tmp != S:
            start = False
            tmp = S
            i = 0
            while i < len(S) - 1:
                if S[i] == S[i+1]:
                    if i + 2:
                        S = S[:i] + S[i+2 :]
                    else:
                        S = S[:i]
                i += 1
            if tmp == S:
                break
            
        # print(S)
        return S
        
        # return res
        # print(remove_ls)
        
        
#         remove_ls = []
#         for i in range(len(S) - 1):
#             if S[i] == S[i + 1]:
#                 if i not in remove_ls:
#                     remove_ls.append(i)
#                 remove_ls.append(i + 1) 

#             if remove_ls == []:
#                 break

#         res = \"\"
#         for i in range(len(S)):
#             if i not in remove_ls:
#                 res += S[i]
#         S = res    
#         start = False


class Solution:
    def removeDuplicates(self, S: str) -> str:
        count = 1
        S = list(S)
        while count != 0:
            x = 0
            while x < (len(S) - 1):
                if S[x] == S[x + 1]:
                    S.pop(x)
                    S.pop(x)
                    if x > 0:
                        x -= 1
                    count += 1
                x += 1
            if count > 1:
                count = 1
            else:
                count = 0
        return(''.join(S))


class Solution:
    def removeDuplicates(self, S: str) -> str:
        st=list(S)
        ud=1
        while ud==1:
            ud=0
            i=1
            while i <= len(st)-1:
                if st[i]==st[i-1]:
                    st.pop(i)
                    st.pop(i-1)
                    ud=1
                i+=1
        return ''.join(st)       

class Solution:
    def removeDuplicates(self, S: str) -> str:
        if len(S) < 2:
            return S
        newS = ''
        count = 1
        while len(S) > 1:
            newS = ''
            chain = False
            for i in range(1, len(S)):
                if S[i] != S[i-1]:
                    if not chain:
                        newS += S[i-1]
                    else:
                        if count % 2 == 1:
                            newS += S[i-1]
                    chain = False
                    count = 1
                else:
                    chain = True
                    count += 1
            if not chain:
                newS += S[-1]
            else:
                if count % 2 == 1:
                    newS += S[-1]
            if newS == S:
                return S
            S = newS
            #print(S)
        return S


class Solution:
    def removeDuplicates(self, S: str) -> str:
        stack = []
        for i in S:
            if stack:
                if stack[-1] == i:
                    stack.pop()
                else:
                    stack.append(i)
            else:
                stack.append(i)
        return ''.join(stack)

class Char(object):
    def __init__(self, val):
        self.val = val
        self.count = 1
        
class Solution:
    def removeDuplicates(self, S: str) -> str:
        '''
        similar to 1D candy crush
        '''
        if len(S) == 0:
            return S
        
        stack = [Char(S[0])]
        k = 2 #duplicate
        
        n = len(S)
        
        for i in range(1, n):
            if stack and stack[-1].val == S[i]:
                stack[-1].count += 1
                
                if stack[-1].count == k:
                    stack.pop()
            else:
                stack.append(Char(S[i]))
        
        output = ''
        while stack:
            char = stack.pop()
            output = char.val*char.count + output
        
        return output
        



class Solution:
    def removeDuplicates(self, S: str) -> str:
        
        def remove_once(S):
            i = 0
            res = ''
            while i<len(S)-1:
                if S[i]!=S[i+1]:
                    res += S[i]
                    i += 1
                else:
                    i += 2
            if i==len(S)-1:
                res += S[i]
            return res
        
        previous_string = S
        removed_string = remove_once(S)
        while removed_string!=previous_string:
            previous_string = removed_string
            removed_string = remove_once(previous_string)
            
        return removed_string

class Solution:
    def removeDuplicates(self, S: str) -> str:
        letters = list(S) + ['#']
        while True:
            nLetters = []
            i = 0
            while i < len(letters) - 1:
                if letters[i] != letters[i + 1]:
                    nLetters.append(letters[i])
                    i += 1
                else:
                    i += 2

            if len(nLetters) + 1 == len(letters): 
                break
            letters = nLetters + ['#']
        return ''.join(letters[:-1])
                
        


class Solution:
    def removeDuplicates(self, S: str) -> str:
        i = 0
        repeat = True
        while repeat:
            repeat = False
            new = ''
            while i < len(S):
                if i < len(S)-1 and S[i] == S[i+1]:
                    i += 2
                    repeat = True
                else:
                    new += S[i]
                    i += 1
            S = new
            i = 0
        return S

class Solution:
    def removeDuplicates(self, S: str) -> str:
        def remove(s):
            if len(s) <= 1:
                return s
            i = 0
            s = s + '#'
            res = ''
            while i < len(s) - 1:
                if s[i] != s[i + 1]:
                    res += s[i]
                else:
                    j = i
                    while j < len(s) - 1 and s[j] == s[j + 1]:
                        j += 1
                    if (j - i) % 2 == 0:
                        res += s[j - 1]
                    i = j
                i += 1
            return res
        
        prev = S
        cur = remove(S)
        while cur != prev:
            prev = cur
            cur = remove(prev)
        
        return cur

class Solution:
    def removeDuplicates(self, S: str) -> str:
        cur = list(S)
        while True:
            next_l = []
            i = 0
            while i < len(cur):
                if i < len(cur) - 1 and cur[i] == cur[i + 1]:
                    i += 2
                    continue
                next_l.append(cur[i])
                i += 1
            if len(next_l) == len(cur):
                return ''.join(next_l)
            cur = next_l
        
        return ''


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

class Solution:
    def removeDuplicates(self, S: str) -> str:
        if len(S) <= 1:
            return S
        
        duplicateFound = True
        output = []
        
        while duplicateFound:
            duplicateFound = False
            i = 0
            while i < len(S):
                if i < len(S) - 1 and S[i] == S[i + 1]:
                    duplicateFound = True
                    i += 2
                    continue
                
                output.append(S[i])
                i += 1            
            
            S = output
            output = []
        
        return ''.join(S)

class Char(object):
    def __init__(self, val):
        self.val = val
        self.count = 1
        
class Solution:
    def removeDuplicates(self, S: str) -> str:
        '''
        similar to 1D candy crush
        This is stack mehod but slightly slower than stack approach in solutions. With this method
            we could solve for duplicates > 2 (adjust k - look 2 submission)
        '''
        if len(S) == 0:
            return S
        
        stack = [Char(S[0])]
        k = 2 #duplicate
        
        n = len(S)
        
        for i in range(1, n):
            if stack and stack[-1].val == S[i]:
                stack[-1].count += 1
                
                if stack[-1].count == k:
                    stack.pop()
            else:
                stack.append(Char(S[i]))
        
        output = ''
        while stack:
            char = stack.pop()
            output = char.val*char.count + output
        
        return output
        



class Solution:
    def removeDuplicates(self, S: str) -> str:
        if S.count(S[0]) == len(S):
            if len(S)%2==0:
                return ''
            else:
                return S[0]
        while True:
            Sbuffer = S[0]
            new_string = S[0]
            for i in S[1:]:
                if i != Sbuffer:
                    new_string += i
                    Sbuffer = i
                else:
                    new_string = new_string[:-1]
                    Sbuffer = ' '
            numlist = [i for i in range(0, len(S)-1)]
            list1 = list(filter(lambda x: S[x+1] == S[x], numlist))
            if list1:
                S = new_string
            else:
                break
        return new_string

def remove_dupes(s):
    i = 0
    out = []
    while i < len(s):
        if i + 1 < len(s) and s[i] == s[i + 1]:
            i += 2
        else:
            out.append(s[i])
            i += 1
    return ''.join(out)
        
    
class Solution:
    def removeDuplicates(self, s: str) -> str:
        prev = None
        while s != prev:
            s, prev = remove_dupes(s), s
        return s
            


class Solution:
    def removeDuplicates(self, S: str) -> str:
        
        prev = S
        
        while True:
            
            i = 0
            
            s = ''
            
            while i < len(prev):
                
                if i != len(prev) - 1 and prev[i] == prev[i + 1]:
                    
                    i += 2
                    
                else:
                    
                    s += prev[i]
                    i += 1
                    
          
            if prev == s:
                
                break
                
            prev = s
                
        return s

class Solution:
    def removeDuplicates(self, S: str) -> str:
        found = True
        while(found):
            found = False
            for i in range(len(S)-1):
                if i >= len(S) - 1:
                    break
                elif S[i] == S[i+1]:
                    found = True
                    S = S[:i] + S[i+2:]
                    i -= 2
        return S

from itertools import groupby

class Solution:
    def removeDuplicates(self, S: str) -> str:
        
        uncompleted = True
        while uncompleted:
            uncompleted = False
            tmp = ['']
            for key, grp in groupby(S):
                letters = list(grp)
                if len(letters) == 1:
                    tmp.extend(letters)
                else:
                    tmp.append(key * (len(letters) - 2))
                    uncompleted = True
            S = ''.join(tmp)
        return S

class Solution:
    def removeDuplicates(self, S: str) -> str:
        i, n = 0, len(S)
        for j in range(0, n):
            #S[i] = S[j]
            S = S[:i] + S[j] + S[i + 1:]
            if i > 0 and S[i - 1] == S[i]:
                i -= 2
            i += 1
        return S[:i]


class Solution:
    def removeDuplicates(self, S: str) -> str:
        stack = ['']
        for s in S:
            if s==stack[-1]:
                stack = stack[:-1]
            else:
                stack+=[s]
        return ''.join(stack[1:])

class Solution:
    def removeDuplicates(self, S: str) -> str:
        stack = []
        for elem in S:
            if stack == []:
                stack.append(elem)
            elif stack[-1] == elem:
                stack = stack[:-1]
            else:
                stack.append(elem)
        return ''.join(stack)