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.

Source: leetcode | Difficulty: EASY
Tags: String algorithms

Data structures

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]
		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:
		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
		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:
		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 = []
		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])
			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


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
		return S


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]
					elif count % 2 == 1:
						newS += S[i - 1]
					chain = False
					count = 1
				else:
					chain = True
					count += 1
			if not chain:
				newS += S[-1]
			elif count % 2 == 1:
				newS += S[-1]
			if newS == S:
				return S
			S = newS
		return S


class Char(object):

	def __init__(self, val):
		self.val = val
		self.count = 1

class Solution:

	def removeDuplicates(self, S: str) -> str:
		if len(S) == 0:
			return S
		stack = [Char(S[0])]
		k = 2
		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:
		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 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 = 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)