Our geek loves to play with strings, Currently, he is trying to reduce the size of a string by recursively removing all the consecutive duplicate pairs. In other words, He can apply the below operations any number of times.
	Remove all the consecutive duplicate pairs and concatenate the remaining string to replace the original string.
Your task is to find the string with minimum length after applying the above operations.
Note: If the string length become zero after applying operations, return "-1" as a string.
Example 1:
Input:
aaabbaaccd
Output: 
ad
Explanation: 
Remove (aa)abbaaccd =>abbaaccd
Remove a(bb)aaccd => aaaccd
Remove (aa)accd => accd
Remove a(cc)d => ad
Example 2:
Input: 
aaaa
Output: 
Empty String
Explanation: 
Remove (aa)aa => aa
Again removing pair of duplicates then (aa) 
will be removed and we will get 'Empty String'.
Your Task:
This is a function problem. You only need to complete the function removePair() that takes a string as a parameter and returns the modified string. Return "-1" if the whole string is deleted.
Expected Time Complexity: O(N)
Expected Auxiliary Space: O(N)
Constraints:
1 <= |str| <= 10^{4}

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Data structures

Starter code: #User function Template for python3



class Solution:

    

    #Function to remove pair of duplicates from given string using Stack.

    def removePair(self,s):

        # code here

Solutions:
class Solution:

	def removePair(self, S):
		s = []
		for i in S:
			if s and s[-1] == i:
				s.pop()
			else:
				s.append(i)
		if len(s) == 0:
			return -1
		else:
			return ''.join(s)


class Solution:

	def removePair(self, S):
		st = []
		for i in range(len(S)):
			if st and st[-1] == S[i]:
				st.pop()
			else:
				st.append(S[i])
		if st:
			return ''.join(st)
		return -1


class Solution:

	def removePair(self, s):
		st = []
		for i in s:
			if st and st[-1] == i:
				st.pop()
			else:
				st.append(i)
		res = ''.join(st)
		if not res:
			return -1
		return res


class Solution:

	def removePair(self, s):
		stack = []
		i = 0
		while i < len(s):
			if len(stack) > 0 and stack[-1] == s[i]:
				stack.pop()
				i += 1
			else:
				stack.append(s[i])
				i += 1
		if len(stack) == 0:
			return -1
		return ''.join(stack)


class Solution:

	def removePair(self, s):
		l = []
		for i in s:
			if len(l) == 0:
				l.append(i)
			elif l[-1] == i:
				l.pop()
			else:
				l.append(i)
		if len(l) == 0:
			return -1
		else:
			return ''.join(l)


class Solution:

	def removePair(self, s):
		flag = False
		while flag == False:
			for i in range(1, len(s)):
				if s[i - 1] == s[i]:
					s = s.replace(s[i - 1] + s[i], '')
					flag = True
					break
			if flag == True:
				flag = False
			else:
				break
		if s:
			return s
		return -1


class Solution:

	def removePair(self, s):
		stack = []
		for i in range(len(s)):
			if not stack:
				stack.append(s[i])
			elif stack and s[i] == stack[-1]:
				stack.pop()
			else:
				stack.append(s[i])
		return ''.join(stack) if stack else -1


class Solution:

	def removePair(self, s):
		stack = []
		for c in s:
			if stack and stack[-1] == c:
				stack.pop()
			else:
				stack.append(c)
		if stack:
			return ''.join(stack)
		else:
			return -1


class Solution:

	def removePair(self, s):
		stack = []
		for i in s:
			if stack and stack[-1] == i:
				stack.pop()
			else:
				stack.append(i)
		c = ''
		if not stack:
			return -1
		while stack:
			c += stack.pop()
		c = c[::-1]
		return c


class Solution:

	def removePair(self, s):
		li = []
		lis = list(s)
		for item in lis:
			if li and li[-1] == item:
				li.pop()
			else:
				li.append(item)
		result = ''.join(li)
		if result:
			return result
		return -1


class Solution:

	def removePair(self, s):
		i = 0
		s = list(s)
		while i < len(s) - 1 and len(s) != 0:
			if s[i] == s[i + 1]:
				s.pop(i)
				s.pop(i)
				i = -1
			i += 1
		if len(s) == 0:
			return '-1'
		return ''.join(s)


class Solution:

	def removePair(self, s):
		stk = []
		i = 0
		ans = ''
		while i < len(s):
			if len(stk) == 0:
				stk.append(s[i])
				i += 1
			elif stk[-1] == s[i]:
				while len(stk) > 0 and i < len(s) and (stk[-1] == s[i]):
					stk.pop()
					i += 1
				if i == len(s):
					break
				else:
					stk.append(s[i])
					i += 1
			else:
				stk.append(s[i])
				i += 1
		if len(stk) == 0:
			return -1
		while len(stk) != 0:
			ans += stk.pop()
		return ans[::-1]


class Solution:

	def removePair(self, s):
		stack = []
		for i in s:
			if len(stack) == 0:
				stack.append(i)
			elif stack[-1] == i:
				stack.pop(-1)
			else:
				stack.append(i)
		ans = ''
		for i in stack:
			ans += i
		if ans == '':
			return -1
		return ans


class Solution:

	def removePair(self, s):
		st = []
		i = 0
		while i < len(s):
			if len(st) == 0 or s[i] != st[-1]:
				st.append(s[i])
				i += 1
			else:
				st.pop()
				i += 1
		else:
			short_string = ''
			for i in st:
				short_string += str(i)
			if len(short_string) == 0:
				return -1
			else:
				return short_string


class Solution:

	def removePair(self, s):
		stack = []
		for i in s:
			if stack == []:
				stack.append(i)
			elif stack[-1] == i:
				stack.pop()
			else:
				stack.append(i)
		if stack:
			return ''.join(stack)
		return -1


from collections import deque

class Solution:

	def removePair(self, s):
		find_string = deque()
		for ch in s:
			if len(find_string) <= 0:
				find_string.append(ch)
			elif find_string[-1] == ch:
				find_string.pop()
			else:
				find_string.append(ch)
		if len(find_string) <= 0:
			return -1
		else:
			return ''.join(find_string)


class Solution:

	def removePair(self, s):
		stack = []
		stack.append(s[0])
		curr_index = 1
		while curr_index < len(s):
			if len(stack) == 0:
				stack.append(s[curr_index])
			elif s[curr_index] == stack[-1]:
				stack.pop()
			else:
				stack.append(s[curr_index])
			curr_index += 1
		ans = ''
		for char in stack:
			ans += char
		if len(ans) == 0:
			ans = '-1'
		return ans


class Solution:

	def removePair(self, s):
		stack = []
		n = len(s)
		count = 0
		for i in range(n):
			if stack == []:
				stack = [s[i]]
				count += 1
			elif stack[-1] == s[i]:
				stack.pop()
				count -= 1
				while count >= 2:
					if stack[-1] == stack[-2]:
						stack.pop()
						stack.pop()
						count -= 2
					else:
						break
			else:
				stack.append(s[i])
				count += 1
		if count == 0:
			return -1
		return ''.join(stack)


from functools import reduce

class Solution:

	def removePair(self, s):
		stack = []
		for ch in s:
			if len(stack) == 0:
				stack.append([ch, 1])
			elif stack[-1][0] == ch:
				stack[-1][1] += 1
				if stack[-1][1] == 2:
					stack.pop()
			else:
				stack.append([ch, 1])
		return -1 if len(stack) == 0 else ''.join([i[0] for i in stack])


class Solution:

	def removePair(self, s):
		ans = ''
		st = ['0', s[0]]
		l = len(s)
		for i in range(1, l):
			if st[-1] == s[i]:
				st.pop()
				flag = True
			else:
				st.append(s[i])
		if st != ['0']:
			ans = ''.join(st[1:])
		else:
			ans = -1
		return ans


class Solution:

	def removePair(self, s):
		temp = []
		for x in s[:]:
			if temp:
				if temp[-1] == x:
					temp.pop()
				else:
					temp.append(x)
			else:
				temp.append(x)
		return ''.join(temp) if temp else -1


class Solution:

	def removePair(self, s):
		d = []
		p = ''
		for i in range(len(s)):
			if len(d) == 0:
				d.append(s[i])
			elif d[-1] != s[i]:
				d.append(s[i])
			elif d[-1] == s[i]:
				d.pop()
		for j in d:
			p += j
		if p:
			return p
		else:
			return -1


class Solution:

	def removePair(self, s):
		li = list(s)
		i = 0
		while i < len(li) - 1:
			if li[i] == li[i + 1]:
				li.pop(i + 1)
				li.pop(i)
				if i != 0:
					i = i - 1
			else:
				i = i + 1
		if len(li) != 0:
			return ''.join(li)
		else:
			return -1


class Solution:

	def removePair(self, s):
		dup_index = self.checkDuplicates(s)
		while dup_index < len(s) - 1:
			s = s[0:dup_index] + s[dup_index + 2:]
			dup_index = self.checkDuplicates(s)
		if len(s) > 0:
			return s
		else:
			return -1

	def checkDuplicates(self, s):
		i = 0
		for i in range(0, len(s) - 1):
			if s[i] == s[i + 1]:
				return i
		return i + 1


class Solution:

	def removePair(self, s):
		l = []
		l.append(s[0])
		for i in range(1, len(s)):
			try:
				if l[-1] == s[i]:
					l.pop()
				else:
					l.append(s[i])
			except IndexError:
				l.append(s[i])
		if len(l) == 0:
			return -1
		return ''.join(l)


class Solution:

	def removePair(self, s):
		stack = []
		for ele in s:
			if len(stack) == 0:
				stack.append(ele)
			elif stack[-1] != ele:
				stack.append(ele)
			elif stack[-1] == ele:
				stack.pop()
			else:
				pass
		if len(stack) == 0:
			return -1
		return ''.join(stack)


class Solution:

	def removePair(self, s):
		i = 0
		ans = ''
		while i < len(s):
			if i + 1 >= len(s):
				if s:
					return s
				else:
					return -1
			if s[i + 1] == s[i]:
				count = 0
				temp = s[i]
				j = i
				while j < len(s) and temp == s[j]:
					count += 1
					j += 1
				if count % 2 != 0:
					s = s[:i] + s[j - 1:]
					if i != 0:
						i -= 1
					continue
				else:
					s = s[:i] + s[j:]
					if i != 0:
						i -= 1
					continue
			i += 1
		if s:
			return s
		else:
			return -1


class Solution:

	def removePair(self, s):
		l = []
		for i in s:
			if not l:
				l.append(i)
			elif l[-1] == i:
				l.pop()
			else:
				l.append(i)
		new = ''.join(l)
		return new if new != '' else -1


class Solution:

	def removePair(self, s):
		l1 = []
		for i in range(len(s)):
			if l1 == []:
				l1.append(s[i])
			elif l1[-1] == s[i]:
				l1.pop()
			else:
				l1.append(s[i])
		s1 = ''.join(l1)
		if s1 == '':
			return -1
		else:
			return s1


class Solution:

	def removePair(self, s):
		l = []
		n = len(s)
		if n == 1:
			return s
		i = 0
		k = -1
		while i < n:
			if k == -1:
				l.append(s[i])
				k += 1
			else:
				t = l[k]
				if t == s[i]:
					l.pop(k)
					k -= 1
				else:
					l.append(s[i])
					k += 1
			i += 1
		if k == -1:
			return '-1'
		else:
			r = ''
			for i in l:
				r += i
			return r


class Solution:

	def removePair(self, s):
		i = 1
		s = list(s)
		A = [s[0]]
		for i in range(1, len(s)):
			if len(A) == 0:
				A.append(s[i])
			elif s[i] == A[-1]:
				A.pop()
			else:
				A.append(s[i])
		if len(A) == 0:
			return -1
		return ''.join(A)


class Solution:

	def removePair(self, s):
		stack = [' '] * len(s)
		top = -1
		for x in s:
			if top == -1 or stack[top] != x:
				top += 1
				stack[top] = x
			elif x == stack[top]:
				top -= 1
		s = ''
		for i in range(0, top + 1):
			s = s + stack[i]
		if top == -1:
			return -1
		return s


class Solution:

	def removePair(self, s):
		stack = []
		i = 0
		while i < len(s):
			if len(stack) == 0:
				stack.append(s[i])
			elif s[i] == stack[-1]:
				stack.pop()
			else:
				stack.append(s[i])
			i += 1
		ans = ''
		while stack:
			a = stack.pop()
			ans = a + ans
		if ans == '':
			return -1
		return ans


class Solution:

	def removePair(self, s):
		n = len(s)
		(ans, i) = ([s[0]], 1)
		while i < len(s):
			if len(ans) > 0:
				if s[i] == ans[-1]:
					ans.pop()
					n -= 2
				else:
					ans.append(s[i])
			else:
				ans.append(s[i])
			i += 1
		if n == 0:
			return -1
		return ''.join(ans)


class Solution:

	def removePair(self, s):
		stk = [-1]
		top = 0
		for i in s:
			if stk[top] == i:
				stk.pop(top)
				top -= 1
			else:
				top += 1
				stk.append(i)
		if len(stk) == 1:
			return -1
		else:
			st = ''
			l = len(stk)
			for i in range(1, l):
				st += stk[i]
			return st


class Solution:

	def removePair(self, s):
		i = 0
		s = s + '.'
		ans = ['' for i in range(len(s))]
		ans1 = 0
		while i < len(s) - 1:
			if s[i] == s[i + 1]:
				i += 2
			else:
				ans[ans1] = s[i]
				ans1 += 1
				if ans[ans1 - 1] == ans[ans1 - 2]:
					ans[ans1 - 1] = ''
					ans[ans1 - 2] = ''
					ans1 = ans1 - 2
				i += 1
		ans = ''.join(ans)
		if ans == '':
			return '-1'
		else:
			return ans


class Solution:

	def removePair(self, s):
		stk = []
		for char in s:
			if not stk:
				stk.append(char)
				continue
			if stk[-1] == char:
				stk.pop()
			else:
				stk.append(char)
		if not stk:
			return -1
		return ''.join(stk)


class Solution:

	def removePair(self, s):
		lst = []
		lst.append('@')
		for i in s:
			if lst[len(lst) - 1] != i:
				lst.append(i)
			else:
				lst.pop()
		if len(lst) == 1:
			return -1
		kk = ''
		for i in range(1, len(lst)):
			kk += lst[i]
		return kk


def merge(s1, s2):
	while s1 and s2:
		if s1[-1] == s2[0]:
			s1.pop(-1)
			s2.pop(0)
		else:
			break
	return s1 + s2

def break_pair(s):
	if len(s) == 1:
		return s
	else:
		mid = len(s) // 2
		s1 = break_pair(s[:mid])
		s2 = break_pair(s[mid:])
		s_final = merge(s1, s2)
		return s_final

class Solution:

	def removePair(self, s):
		a = list(s)
		res = break_pair(a)
		return ''.join(res) if res else -1


class Solution:

	def removePair(self, s):
		fg = []
		res = ''
		for i in s:
			f = 0
			while len(fg) > 0 and fg[len(fg) - 1] == i:
				fg.pop(len(fg) - 1)
				f = 1
			if f == 0:
				fg.append(i)
		while len(fg) > 0:
			res = fg[len(fg) - 1] + res
			fg.pop(len(fg) - 1)
		if len(res) == 0:
			return '-1'
		return res


class Solution:

	def removePair(self, s):
		l = []
		for i in range(len(s)):
			if l and l[-1] == s[i]:
				l.pop()
			else:
				l.append(s[i])
		if l:
			return ''.join(l)
		else:
			return '-1'


class Solution:

	def removePair(self, s):
		lexp = list(s)
		stack = []
		out = []
		n = len(lexp)
		top = 0
		stack.append(lexp[0])
		for i in range(1, n):
			if len(stack) > 0:
				if lexp[i] != stack[top]:
					top += 1
					stack.append(lexp[i])
				elif lexp[i] == stack[top]:
					stack.pop()
					top -= 1
			else:
				top += 1
				stack.append(lexp[i])
		if len(stack) == 0:
			return -1
		else:
			return ''.join(stack)


class Solution:

	def removePair(self, s):
		i = 0
		while i < len(s) - 1:
			if s[i] == s[i + 1]:
				s = s[:i] + s[i + 2:]
				i = -1
			i += 1
		if len(s) == 0:
			return '-1'
		return s


class Solution:

	def removePair(self, s):
		res = []
		for i in s:
			if len(res) > 0 and i == res[-1]:
				res.pop()
			else:
				res.append(i)
		if len(res) == 0:
			return -1
		return ''.join(map(str, res))


class Solution:

	def removePair(self, s):
		stack = []
		for ele in s:
			if len(stack) > 0:
				t = stack.pop()
				if t == ele:
					continue
				else:
					stack.append(t)
					stack.append(ele)
			else:
				stack.append(ele)
		if stack == []:
			return '-1'
		return ''.join(stack)


class Solution:

	def removePair(self, s):
		s1 = s
		while True:
			isRemoved = False
			for idx in range(len(s) - 1):
				if s[idx] == s[idx + 1]:
					text2Remove = s[idx] + s[idx + 1]
					s1 = s1.replace(text2Remove, '', 1)
					isRemoved = True
			if isRemoved == False:
				break
			else:
				s = s1
		if len(s1) == 0:
			return -1
		else:
			return s1


class Solution:

	def removePair(self, s):
		arr = []
		for i in s:
			if arr and arr[-1] == i:
				arr.pop()
			else:
				arr.append(i)
		return ''.join(arr) if arr else '-1'


import sys
sys.setrecursionlimit(10 ** 6)

class Solution:

	def removePair(self, s):

		def solve(s):
			if len(s) == 0:
				return ''
			if len(s) == 1:
				return s
			if s[0] == s[1]:
				return solve(s[2:])
			else:
				small = solve(s[1:])
				if small and s[0] == small[0]:
					return small[1:]
				else:
					return s[0] + small
		return solve(s) if len(solve(s)) > 0 else -1


class Solution:

	def removePair(self, s):
		i = 1
		while i < len(s):
			if i == 0:
				i += 1
				continue
			if s[i] == s[i - 1]:
				s = s[:i - 1] + s[i + 1:]
				i -= 1
			else:
				i += 1
		if len(s) == 0:
			return -1
		return s


class Solution:

	def removePair(self, s):
		i = 0
		a = list(s)
		c = len(a)
		s1 = ''
		j = 0
		while i < c:
			if j == 0:
				s1 += s[i]
				j += 1
				i += 1
			else:
				s1 += s[i]
				j += 1
				if s[i] == s1[j - 2]:
					if len(s1) == 2:
						s1 = ''
					else:
						s1 = s1[:len(s1) - 2]
					j -= 2
				i += 1
		if s1 == '':
			return '-1'
		else:
			return s1


class Solution:

	def removePair(self, s):
		stack = []
		ans = ''
		for i in range(len(s)):
			if stack and stack[-1] == s[i]:
				stack.pop()
			else:
				stack.append(s[i])
		if len(stack) == 0:
			return -1
		else:
			while len(stack) > 0:
				ans += stack[-1]
				stack.pop()
		return ans[::-1]


class Solution:

	def removePair(self, s):
		l = []
		for i in s:
			if not l:
				l.append(i)
			elif l[len(l) - 1] == i:
				l.pop()
			else:
				l.append(i)
		k = ''
		if not l:
			return -1
		for i in l:
			k += i
		return k


from collections import deque

class Solution:

	def removePair(self, s):
		que = deque()
		for i in range(len(s)):
			if len(que) < 1:
				que.append(s[i])
			elif que[-1] == s[i]:
				que.pop()
			else:
				que.append(s[i])
		ans = ''
		for i in range(len(que)):
			ans += que.popleft()
		if len(ans) == 0:
			return -1
		return ans


class Solution:

	def removePair(self, s):
		new_s = []
		l = 0
		b = -1
		while l < len(s) - 1:
			if s[l] == s[l + 1]:
				l += 2
			elif b != -1 and s[l] == new_s[b]:
				new_s.pop()
				b -= 1
				l += 1
			else:
				new_s.append(s[l])
				b += 1
				l += 1
		if l < len(s):
			if b != -1 and s[l] == new_s[b]:
				new_s.pop()
				b -= 1
			else:
				new_s.append(s[l])
		if b == -1:
			return b
		else:
			return ''.join(new_s)


class Solution:

	def removePair(self, s):
		st = []
		i = 0
		while i < len(s):
			if len(st) == 0 or st[-1] != s[i]:
				st.append(s[i])
			elif len(st) != 0 and st[-1] == s[i]:
				st.pop()
			i += 1
		t = ''
		for j in st:
			t += j
		if t == '':
			return -1
		return t


class Solution:

	def removePair(self, s):
		stack = []
		top = -1
		for i in range(0, len(s)):
			if len(stack) == 0:
				stack.append(s[i])
				top += 1
			elif stack[top] != s[i]:
				stack.append(s[i])
				top += 1
			else:
				stack.pop()
				top -= 1
		if len(stack) == 0:
			return -1
		return ''.join(stack)