Given a string S, in an operation you can remove 3 consecutive characters which are duplicates and concatenate the rest string. You can perform this operation any number of times. Find the reduced string.
Note: Return '-1' if the string is empty after removing the duplicates.
Example 1:
Input: S = "aabbbaccddddc"
Output: ccdc
Explanation: First remove 3 consecutive
b's and d's and then a's
Example 2:
Input: S = "aabbaccddc"
Output: aabbaccddc
Explanation: No three consecutive 
duplicates exists
Your Task:
You don't need to read input or print anything. Your task is to complete the function remove3ConsecutiveDuplicates() which takes a string S as input and returns the string. 
Expected Time Complexity: O(|S|).
Expected Auxiliary Space: O(|S|).
Constraints:
1 <= |S| <= 10^{5}
S contains lower case English alphabets

Difficulty: EASY
Tags: String algorithms

Data structures
Skill types: Data structures
Expected Time Complexity: O(|S|).
Expected Auxiliary Space: O(|S|).

Starter code:
#User function Template for python3
class Solution:
	def remove3ConsecutiveDuplicates(self, S):
		# code here

Solutions:
class Solution:

	def remove3ConsecutiveDuplicates(self, S):
		stack = []
		for i in S:
			if len(stack) > 1 and stack[-1] == stack[-2] == i:
				stack.pop()
				stack.pop()
			else:
				stack.append(i)
		if len(stack) >= 1:
			return ''.join(stack)
		else:
			return -1


class Solution:

	def remove3ConsecutiveDuplicates(self, S):
		stack = []
		st = ''
		for i in S:
			if stack and stack[-1][0] == i:
				stack[-1][1] += 1
			else:
				stack.append([i, 1])
			if stack[-1][1] == 3:
				stack.pop()
		if len(stack) == 0:
			return -1
		for i in stack:
			st += i[0] * i[1]
		return st


class Solution:

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


class Solution:

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


class Solution:

	def remove3ConsecutiveDuplicates(self, S):
		res = ''
		flag = 1
		while len(S) > 0 and flag == 1:
			flag = 0
			i = 0
			store = S
			res = ''
			while i < len(S) - 2:
				if S[i] == S[i + 1] and S[i + 1] == S[i + 2]:
					flag = 1
					i += 3
					continue
				else:
					res += S[i]
					i += 1
			while i != len(S) and i < len(S):
				res += S[i]
				i += 1
			S = res
		if flag == 1:
			return -1
		else:
			return store


class Solution:

	def remove3ConsecutiveDuplicates(self, S):
		stack = []
		top = -1
		newstring = ''
		if len(S) == 1:
			return S
		for i in range(len(S)):
			if top == -1 or top == 0:
				stack.append(S[i])
				top += 1
			elif S[i] == stack[top] and S[i] == stack[top - 1]:
				stack.pop(top)
				top -= 1
				stack.pop(top)
				top -= 1
			else:
				stack.append(S[i])
				top += 1
		for val in stack:
			newstring += val
		return -1 if len(newstring) == 0 else newstring
if __name__ == '__main__':
	T = int(input())
	for i in range(T):
		S = input()
		ob = Solution()
		answer = ob.remove3ConsecutiveDuplicates(S)
		print(answer)


class Solution:

	def remove3ConsecutiveDuplicates(self, S):
		res = ''
		for i in range(len(S)):
			res += S[i]
			if len(res) >= 3:
				size = len(res)
				if res[size - 1] == res[size - 2] and res[size - 2] == res[size - 3]:
					res = res[0:len(res) - 3]
		return -1 if len(res) == 0 else res


class Solution:

	def remove3ConsecutiveDuplicates(self, S):
		ans = ''
		i = 0
		for i in range(len(S)):
			ans += S[i]
			if len(ans) >= 3:
				n = len(ans)
				if ans[n - 1] == ans[n - 2] and ans[n - 2] == ans[n - 3]:
					ans = ans[:n - 3]
		if len(ans) == 0:
			return '-1'
		else:
			return ans


class Solution:

	def remove3ConsecutiveDuplicates(self, string):
		val = ''
		i = 0
		while i < len(string):
			if i < len(string) - 2 and string[i] * 3 == string[i:i + 3]:
				i += 3
			else:
				val += string[i]
				i += 1
		if len(val) == len(string):
			return val
		elif len(val) == 0:
			return -1
		else:
			return self.remove3ConsecutiveDuplicates(val)


class Solution:

	def remove3ConsecutiveDuplicates(self, S):
		j = 0
		while j < len(S):
			if S == '':
				return -1
			if len(S) < 3:
				return S
			if j >= 2:
				if S[j] == S[j - 1] and S[j] == S[j - 2]:
					S = S.replace(S[j - 2:j + 1], '')
					j = j - 3
				else:
					j += 1
			else:
				j += 1
		return S


class Solution:

	def remove3ConsecutiveDuplicates(self, S):
		v = 0
		while v == 0:
			p = 0
			i = 0
			c = ''
			while i <= len(S) - 1:
				if i < len(S) - 3 and S[i] == S[i + 1] and (S[i + 1] == S[i + 2]):
					i = i + 3
					p = 1
					continue
				if i == len(S) - 3 and S[i] == S[i + 1] and (S[i + 1] == S[i + 2]):
					S = c
					break
				else:
					c = c + S[i]
					i = i + 1
			S = c
			if p == 0:
				v = 1
		if len(S) == 0:
			return '-1'
		return S


class Solution:

	def remove3ConsecutiveDuplicates(self, S):
		stack = []
		for c in S:
			stack.append(c)
			if len(stack) >= 3:
				lastThree = stack[-3:]
				if lastThree[0] == lastThree[1] and lastThree[1] == lastThree[2]:
					stack = stack[:-3]
		if len(stack) == 0:
			return '-1'
		return ''.join(stack)