Given a string s, remove all its adjacent duplicate characters recursively. 
Note: For some test cases, the resultant string would be an empty string. In that case, the function should return the empty string only.
Example 1:
Input:
S = "geeksforgeek"
Output: "gksforgk"
Explanation: 
g(ee)ksforg(ee)k -> gksforgk
Example 2:
Input: 
S = "abccbccba"
Output: ""
Explanation: 
ab(cc)b(cc)ba->abbba->a(bbb)a->aa->(aa)->""(empty string)
Your Task:
You don't need to read input or print anything. Your task is to complete the function rremove() which takes the string S as input parameter and returns the resultant string.
Expected Time Complexity: O(|S|)
Expected Auxiliary Space: O(|S|)
Constraints:
1<=|S|<=10^{5}

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: String algorithms

Data structures

Complete search

Starter code: #User function Template for python3



class Solution:

    def rremove (self, S):

		#code here

Solutions:
class Solution:

	def rremove(self, S):

		def rec(S):
			ans = ''
			n = len(S)
			i = 0
			while i < n:
				if i < n - 1 and S[i] == S[i + 1]:
					while i < n - 1 and S[i] == S[i + 1]:
						i += 1
				else:
					ans += S[i]
				i += 1
			return ans
		s1 = ''
		while len(S) != len(s1):
			s1 = S
			S = rec(S)
		return S


class Solution:

	def rremove(self, s):
		n = len(s)
		word = []
		i = 0
		while i < len(s):
			flag = 0
			while i < n - 1 and s[i] == s[i + 1]:
				i += 1
				flag = 1
			if not flag:
				word.append(s[i])
			i += 1
		if len(word) < n:
			return self.rremove(''.join(word))
		return ''.join(word)


class Solution:

	def rremove(self, S):
		new = [i for i in S]
		st = []
		i = 0
		while i < len(S):
			if st and st[-1] == S[i]:
				while i < len(S) and S[i] == st[-1]:
					i += 1
				st.pop()
			if i < len(S):
				st.append(S[i])
				i += 1
		if new == st:
			return ''.join(new)
		else:
			return self.rremove(''.join(st))


class Solution:

	def rremove(self, S):
		ans = ''
		duplicate = True
		while duplicate:
			i = 0
			duplicate = False
			while i < len(S):
				count = 1
				while i < len(S) - 1 and S[i] == S[i + 1]:
					count += 1
					i += 1
					duplicate = True
				if count == 1:
					ans += S[i]
				i += 1
			if duplicate:
				S = ans
				ans = ''
		return ans


class Solution:

	def remove(self, S):
		ans = ''
		n = len(S)
		i = 0
		while i < n:
			if i < n - 1 and S[i] == S[i + 1]:
				while i < n - 1 and S[i] == S[i + 1]:
					i += 1
			else:
				ans += S[i]
			i += 1
		return ans

	def rremove(self, S):
		temp = ''
		while len(S) != len(temp):
			temp = S
			S = self.remove(S)
		return S


class Solution:

	def rremove(self, S):

		def rems(S):
			i = 0
			ans = []
			while i < len(S):
				if i < len(S) - 1:
					if S[i] == S[i + 1]:
						while i < len(S) - 1 and S[i] == S[i + 1]:
							i = i + 1
					else:
						ans.append(S[i])
				else:
					ans.append(S[i])
				i = i + 1
			return ''.join(ans)
		ans = ''
		k = rems(S)
		while len(ans) != len(k):
			ans = k
			k = rems(ans)
		return k


class Solution:

	def rremove(self, s):
		prev = ''
		temp = ''
		if len(s) < 2:
			return s
		for i in range(len(s) - 1):
			if s[i] == s[i + 1]:
				prev = s[i]
			elif s[i] == prev:
				prev = ''
			else:
				temp += s[i]
		if s[-1] != prev:
			temp += s[-1]
		if len(s) == len(temp):
			return temp
		else:
			return self.rremove(temp)


class Solution:

	def rremove(self, S):
		new = []
		i = 0
		n = len(S)
		while i < len(S):
			temp = 0
			while i < n - 1 and S[i] == S[i + 1]:
				temp = 1
				i += 1
			if temp == 0:
				new.append(S[i])
			i += 1
		if len(new) < n:
			return self.rremove(new)
		return ''.join(new)


class Solution:

	def rremove(self, S):
		sn = len(S)
		is_continue = True
		while is_continue:
			is_continue = False
			buffer = []
			i = 0
			while i < sn:
				j = i + 1
				while j < sn and S[j] == S[i]:
					j += 1
				if j == i + 1:
					buffer.append(S[i])
					i += 1
				else:
					is_continue = True
					i = j
			S = ''.join(buffer)
			sn = len(S)
		return S


class Solution:

	def rremove(self, s):
		res = ''
		i = 0
		while i < len(s):
			if i + 1 < len(s) and s[i] == s[i + 1]:
				i += 1
				while i < len(s) and s[i] == s[i - 1]:
					i += 1
			else:
				res += s[i]
				i += 1
		return res if len(res) == len(s) else self.rremove(res)


class Solution:

	def rremove(self, S):
		n = len(S)
		flag = True
		while flag:
			flag = False
			arr = []
			i = 0
			while i < n:
				j = i + 1
				while j < n and S[j] == S[i]:
					j += 1
				if j == i + 1:
					arr.append(S[i])
					i += 1
				else:
					flag = True
					i = j
			S = ''.join(arr)
			n = len(S)
		return S


class Solution:

	def rremove(self, S):
		q = [S]
		newS = ''
		while len(q):
			root = q.pop(0)
			flg = True
			newS = ''
			i = 0
			while i < len(root):
				j = i + 1
				fl = True
				while j < len(root) and root[i] == root[j]:
					j += 1
					fl = False
					flg = False
				if fl:
					newS += root[i]
				i = j
			q.append(newS)
			if flg:
				break
		return newS


class Solution:

	def rremove(self, S):
		s_list = list(S)
		ns = self._remove(s_list)
		return ''.join(ns)

	def _remove(self, s_lst):
		ns = []
		prv = None
		lprv = None
		for c in s_lst:
			if c != prv:
				ns.append(c)
			elif lprv != c:
				ns.pop()
			lprv = prv
			prv = c
		if len(ns) == len(s_lst):
			return ns
		return self._remove(ns)


class Solution:

	def rremove(self, S):
		if not S:
			return S
		global_dups = 0
		final_string = ''
		i = 0
		while i < len(S):
			duplicates = 0
			j = i + 1
			while j < len(S) and S[j] == S[i]:
				duplicates = 1
				global_dups += 1
				j += 1
			i = j - 1
			if not duplicates:
				final_string += S[i]
			i += 1
		return Solution().rremove(final_string) if global_dups else final_string


class Solution:

	def rremove(self, s):

		def remove(s, old):
			if s == '':
				return s
			elif s == old:
				return s
			old = s
			arr = list(s)
			prev = 0
			for i in range(1, len(s)):
				if arr[i] == arr[i - 1]:
					prev = 1
					arr[i - 1] = ''
				elif prev == 1:
					arr[i - 1] = ''
					prev = 0
			if prev == 1:
				arr[i] = ''
			s = ''.join(arr)
			return remove(s, old)
		return remove(s, '')


class Solution:

	def rremove(self, S):

		def remove(s):
			if s == '':
				return ''
			if len(s) == 1:
				return s
			if s[0] == s[1]:
				new_s = ''
			else:
				new_s = s[0]
			i = 1
			while i < len(s) - 1:
				if s[i] != s[i - 1] and s[i] != s[i + 1]:
					new_s += s[i]
				i += 1
			else:
				if s[-1] != s[-2]:
					new_s += s[-1]
			if s == new_s:
				return s
			else:
				return remove(new_s)
		return remove(S)


class Solution:

	def rremove(self, S):
		if len(S) < 2:
			return S
		i = 0
		j = 1
		is_duplicate = False
		modified = False
		non_duplicates = []
		while j < len(S):
			if S[j] == S[i]:
				j += 1
				is_duplicate = True
			elif is_duplicate:
				i = j
				j += 1
				is_duplicate = False
				modified = True
			else:
				non_duplicates.append(S[i])
				i = j
				j += 1
		if not is_duplicate:
			non_duplicates.append(S[i])
		updated_str = ''.join(non_duplicates)
		if modified:
			return self.rremove(updated_str)
		return updated_str


class Solution:

	def rremove(self, S):
		if len(S) == 0:
			return ''
		length = len(S)
		dupl_nums = 1
		store = []
		i = 0
		while i < length - 1:
			if S[i] == S[i + 1]:
				start_dupl = i
				dupl_nums = 2
				k = i + 2
				while k < len(S) and S[k] == S[i]:
					dupl_nums += 1
					k += 1
				if len(store) == 0:
					store.append(S[0:start_dupl])
				else:
					store.append(S[next_start:start_dupl])
				next_start = i + dupl_nums
				i += dupl_nums
			else:
				i += 1
		if store:
			if next_start < length:
				store.append(S[next_start:])
			new_string = ''.join(store)
			return self.rremove(new_string)
		else:
			return S
		return S


class Solution:

	def rremove(self, s):
		a = ''
		b = ''
		if len(s) < 2:
			return s
		for i in range(len(s) - 1):
			if s[i] == s[i + 1]:
				a = s[i]
			elif s[i] == a:
				a = ''
			else:
				b += s[i]
		if s[-1] != a:
			b += s[-1]
		if len(s) == len(b):
			return b
		else:
			return self.rremove(b)


class Solution:

	def rremove(self, s):
		sm = len(s)
		is_con = True
		while is_con:
			is_con = False
			buf = []
			i = 0
			while i < sm:
				j = i + 1
				while j < sm and s[j] == s[i]:
					j += 1
				if j == i + 1:
					buf.append(s[i])
					i += 1
				else:
					is_con = True
					i = j
			s = ''.join(buf)
			sm = len(s)
		return s


class Solution:

	def rremove(self, S):
		l = len(S)
		a = []
		d = False
		for i in range(len(S)):
			if i == 0:
				if S[i] != S[i + 1]:
					a.append(S[i])
			elif i < len(S) - 1:
				if S[i] != S[i + 1] and S[i] != S[i - 1]:
					a.append(S[i])
			elif S[-1] != S[-2]:
				a.append(S[-1])
		k = ''.join(a)
		for i in range(len(k) - 1):
			if k[i] == k[i + 1]:
				d = True
				break
		if d:
			return self.rremove(k)
		else:
			return k


class Solution:

	def rremove(self, S):
		sn = len(S)
		a = True
		while a:
			a = False
			b = []
			i = 0
			while i < sn:
				j = i + 1
				while j < sn and S[j] == S[i]:
					j += 1
				if j == i + 1:
					b.append(S[i])
					i += 1
				else:
					a = True
					i = j
			S = ''.join(b)
			sn = len(S)
		return S


class Solution:

	def rremove(self, s):
		n = len(s)
		f = True
		while f:
			f = False
			l = []
			i = 0
			while i < n:
				j = i + 1
				while j < n and s[j] == s[i]:
					j = j + 1
				if j == i + 1:
					l.append(s[i])
					i = i + 1
				else:
					f = True
					i = j
			s = ''.join(l)
			n = len(s)
		return s


import re

class Solution:

	def rremove(self, S):
		n = len(S)
		k = True
		while k:
			k = False
			b = []
			i = 0
			while i < n:
				j = i + 1
				while j < n and S[j] == S[i]:
					j += 1
				if j == i + 1:
					b.append(S[i])
					i += 1
				else:
					k = True
					i = j
			S = ''.join(b)
			n = len(S)
		return S


class Solution:

	def rremove(self, S):
		ans = ''
		if len(S) <= 1:
			return S
		for i in range(0, len(S)):
			if i == 0:
				if S[i] != S[i + 1]:
					ans = ans + S[i]
			elif i == len(S) - 1:
				if S[i] != S[i - 1]:
					ans = ans + S[i]
			elif S[i] != S[i - 1] and S[i] != S[i + 1]:
				ans = ans + S[i]
		if len(S) != len(ans):
			return self.rremove(ans)
		return ans


class Solution:

	def rremove(self, s):
		a = []
		i = 0
		n = len(s)
		while i < len(s):
			temp = 0
			while i < n - 1 and s[i] == s[i + 1]:
				temp = 1
				i += 1
			if temp == 0:
				a.append(s[i])
			i += 1
		if len(a) < n:
			return self.rremove(a)
		return ''.join(a)


class Solution:

	def rremove(self, S):
		l = len(S)
		con = True
		while con:
			con = False
			buf = []
			i = 0
			while i < l:
				j = i + 1
				while j < l and S[j] == S[i]:
					j += 1
				if j == i + 1:
					buf.append(S[i])
					i += 1
				else:
					con = True
					i = j
			S = ''.join(buf)
			l = len(S)
		return S


class Solution:

	def rremove(self, s):
		s1 = ''
		while len(s1) != len(s):
			s1 = s
			s = self.fun(s)
		return s

	def fun(self, s):
		ans = ''
		n = len(s)
		i = 0
		while i < n:
			if i < n - 1 and s[i] == s[i + 1]:
				while i < n - 1 and s[i] == s[i + 1]:
					i += 1
			else:
				ans += s[i]
			i += 1
		return ans


class Solution:

	def rremove(self, s):
		p = t = ''
		if len(s) < 2:
			return s
		for i in range(len(s) - 1):
			if s[i] == s[i + 1]:
				p = s[i]
			elif s[i] == p:
				p = ''
			else:
				t += s[i]
		if s[-1] != p:
			t += s[-1]
		if len(s) == len(t):
			return t
		else:
			return self.rremove(t)


class Solution:

	def rremove(self, S):
		newS = ''
		if len(S) == 0:
			return ''
		if len(S) == 1:
			return S
		c = '%'
		S += '&'
		for i in range(len(S) - 1):
			if S[i] == S[i + 1]:
				c = S[i]
				newS += '#'
			elif S[i] == c:
				newS += '#'
				c = '%'
			else:
				newS += S[i]
		newS = newS.replace('#', '')
		S = S[:-1]
		if len(newS) == len(S):
			return S
		return self.rremove(newS)


class Solution:

	def rremove(self, S):

		def rem(s):
			l = [s[0]]
			i = 1
			n = len(s)
			while i < n:
				if s[i] != s[i - 1]:
					l += [s[i]]
				else:
					p = s[i]
					j = i + 1
					if j < n:
						while j < n:
							if s[j] != p:
								l.pop()
								l += [s[j]]
								i = j
								break
							j += 1
					else:
						l.pop()
				i += 1
			return ''.join(l)
		b = S[:]
		while True:
			f = 1
			if b == '' or len(b) == 1:
				return b
			if len(b) == 2:
				if b[0] == b[1]:
					return ''
				else:
					return b
			for i in range(1, len(b)):
				if b[i] == b[i - 1]:
					f = 0
					break
			if f == 0:
				b = rem(b)
			else:
				return b