Given a string S which consists of only lowercase English alphabets, you have to perform the below operations:
If the string S contains any repeating character, remove the first repeating character and reverse the string and again perform the above operation on the modified string, otherwise, you stop.
You have to find the final string.
Example 1:
Input: S = "abab"
Output: ba
Explanation:
In 1st operation: The first repeating 
character is a. After Removing the first 
character, S = "bab". After Reversing the 
string, S = "bab".
In 2nd operation: The first repeating 
character is b. After Removing the first 
character, S = "ab". After Reversing the 
string, S = "ba".
Now the string S does not contain any 
repeating character.
Example 2:
Input: S = "dddd"
Output: d
Explanation:
In 1st operation: The first repeating character 
is d. After Removing the first character, 
S = "ddd". After Reversing the string, S = "ddd". 
In 2nd operation: Similarly, S="dd".
In 3rd operation: Similarly, S="d".
Now the string S does not contain any repeating character.
Your Task:  
You don't need to read input or print anything. Your task is to complete the function removeReverse( ) which accepts a string S input parameter and returns the modified string.
Expected Time Complexity: O(|S|)
Expected Auxiliary Space: O(K), K <= 26.
Constraints:
The string contains only lowercase English alphabets.
1 < |S| < 10^{5}
|S| denotes the length of the string S.

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: String algorithms

Data structures

Amortized analysis

Starter code: #User function Template for python3

class Solution:

    def removeReverse(self, S): 

        #code here

Solutions:
class Solution:

	def removeReverse(self, S):
		S = list(S)
		dict1 = dict()
		i = 0
		j = len(S) - 1
		nd = ''
		nd2 = ''
		beg = True
		for i in S:
			dict1.setdefault(i, 0)
			dict1[i] += 1
		i = 0
		j = len(S) - 1
		cnt = 0
		while i <= j:
			if beg:
				if dict1[S[i]] > 1:
					dict1[S[i]] -= 1
					i += 1
					beg = False
					cnt += 1
				else:
					nd += S[i]
					i += 1
			elif dict1[S[j]] > 1:
				dict1[S[j]] -= 1
				j -= 1
				beg = True
				cnt += 1
			else:
				nd2 = S[j] + nd2
				j -= 1
		return (nd + nd2)[::-1] if cnt % 2 else nd + nd2


class Solution:

	def removeReverse(self, S):
		mapVal = {}
		for letter in S:
			mapVal[letter] = mapVal.get(letter, 0) + 1
		stringar = list(S)
		rev = False
		i = 0
		j = len(stringar) - 1
		while i < j:
			if rev == False:
				if mapVal[stringar[i]] > 1:
					mapVal[stringar[i]] -= 1
					stringar.pop(i)
					rev = not rev
					j = len(stringar) - 1
				else:
					i += 1
			elif mapVal[stringar[j]] > 1:
				mapVal[stringar[j]] -= 1
				stringar.pop(j)
				rev = not rev
			else:
				j -= 1
		if rev:
			stringar = stringar[::-1]
		return ''.join(stringar)


class Solution:

	def removeReverse(self, S):
		D = {}
		S = list(S)
		for i in range(len(S)):
			if S[i] not in D.keys():
				D[S[i]] = 1
			else:
				D[S[i]] += 1
		l = 0
		r = len(S) - 1
		flag = 0
		while l <= r:
			if flag == 0:
				if D[S[l]] == 1:
					l += 1
				else:
					D[S[l]] -= 1
					S[l] = '#'
					l += 1
					flag = 1
			elif D[S[r]] == 1:
				r -= 1
			else:
				D[S[r]] -= 1
				S[r] = '#'
				r -= 1
				flag = 0
		D = ''
		if flag == 1:
			S = S[::-1]
		for i in range(len(S)):
			if S[i] != '#':
				D += S[i]
		return D


class Solution:

	def removeReverse(self, S):
		L = len(S)
		D = True
		start = True
		while D:
			newstr = self.remRev(S, L, start)
			S = newstr[0]
			D = newstr[1]
			start = not start
			L -= 1
		if start:
			return S[::-1]
		return S

	def remRev(self, S, L, start):
		if start:
			for i in range(L):
				for j in range(L - 1, i, -1):
					if S[i] == S[j]:
						return (S[:i] + S[i + 1:], True)
			return (S, False)
		else:
			for i in range(L - 1, -1, -1):
				for j in range(i):
					if S[i] == S[j]:
						return (S[:i] + S[i + 1:], True)
			return (S, False)


class Solution:

	def removeReverse(self, s):
		(h, d) = ([0] * 26, 1)
		for i in range(len(s)):
			h[ord(s[i]) - 97] += 1
		i = 0
		while 0 <= i < len(s):
			if h[ord(s[i]) - 97] > 1:
				h[ord(s[i]) - 97] -= 1
				s = s[:i] + s[i + 1:]
				i = len(s) - 1 if d == 1 else 0
				d *= -1
			else:
				i += d
		return s if d > 0 else s[::-1]


class Solution:

	def removeReverse(self, S):
		s = []
		s[:0] = S
		freq = [0] * 26
		for i in s:
			freq[ord(i) - ord('a')] += 1
		l = 0
		r = len(s) - 1
		f = 0
		while l <= r:
			if f == 0:
				if freq[ord(s[l]) - ord('a')] == 1:
					l += 1
				else:
					freq[ord(s[l]) - ord('a')] -= 1
					s[l] = '#'
					l += 1
					f ^= 1
			elif freq[ord(s[r]) - ord('a')] == 1:
				r -= 1
			else:
				freq[ord(s[r]) - ord('a')] -= 1
				s[r] = '#'
				r -= 1
				f ^= 1
		if f == 1:
			s.reverse()
		ans = ''
		for i in s:
			if i != '#':
				ans += i
		return ans


class Solution:

	def removeReverse(self, S):
		s = list(S)
		n = len(s)
		from collections import Counter
		cnt = Counter(s)
		l = 0
		r = n - 1
		lr = 0
		while l < n and r >= 0:
			if lr == 0:
				if cnt[s[l]] >= 2:
					cnt[s[l]] -= 1
					s[l] = '_'
					lr = 1
				l += 1
			else:
				if cnt[s[r]] >= 2:
					cnt[s[r]] -= 1
					s[r] = '_'
					lr = 0
				r -= 1
		ret = [x for x in s if x != '_']
		if lr == 1:
			ret = ret[::-1]
		return ''.join(ret)


class Solution:

	def removeReverse(self, S):
		(i, j) = (0, len(S) - 1)
		_map = [0] * 26
		flag = True
		cnt = 0
		for ch in S:
			_map[ord(ch) - ord('a')] += 1
		(begin, end) = ('', '')
		while i <= j:
			if flag:
				ch = S[i]
				i += 1
			else:
				ch = S[j]
				j -= 1
			if _map[ord(ch) - ord('a')] > 1:
				_map[ord(ch) - ord('a')] -= 1
				cnt += 1
				flag = not flag
			elif flag:
				begin += ch
			else:
				end = ch + end
		ans = begin + end
		if cnt % 2 == 1:
			ans = ans[::-1]
		return ans


class Solution:

	def removeReverse(self, S):
		d = {}
		for i in S:
			d[i] = d.get(i, 0) + 1
		n = len(S)
		l = list(S)
		(i, j) = (0, n - 1)
		flag = True
		while i <= j:
			if flag:
				if d[l[i]] > 1:
					d[l[i]] -= 1
					l[i] = ''
					flag = False
				i += 1
			else:
				if d[l[j]] > 1:
					d[l[j]] -= 1
					l[j] = ''
					flag = True
				j -= 1
		if flag:
			ans = ''.join(l)
		else:
			l.reverse()
			ans = ''.join(l)
		return ans


class Solution:

	def removeReverse(self, S):
		n = len(S)
		freq = {}
		for i in range(n):
			if S[i] in freq.keys():
				freq[S[i]] += 1
			else:
				freq[S[i]] = 1
		(left, right) = (0, n - 1)
		flag = True
		result = ''
		while left < right:
			if flag == True:
				while left < len(S) and freq[S[left]] == 1:
					result += S[left]
					left += 1
				if left >= right:
					break
				freq[S[left]] -= 1
				S = S[:left] + S[left + 1:]
				right -= 1
				flag = False
			else:
				while right >= 0 and freq[S[right]] == 1:
					result += S[right]
					right -= 1
				if left >= right:
					break
				freq[S[right]] -= 1
				S = S[:right] + S[right + 1:]
				right -= 1
				flag = True
		if flag == False:
			return S[::-1]
		return S


class Solution:

	def removeReverse(self, S):
		dic = {}
		n = len(S)
		for i in S:
			if i in dic:
				dic[i] += 1
			else:
				dic[i] = 1
		start = 0
		stop = n - 1
		rev = False
		st1 = ''
		st2 = ''
		while start <= stop:
			if rev == False:
				if dic[S[start]] == 1:
					st1 += S[start]
					start += 1
				else:
					dic[S[start]] -= 1
					start += 1
					rev = True
			elif dic[S[stop]] == 1:
				st2 = S[stop] + st2
				stop -= 1
			else:
				dic[S[stop]] -= 1
				stop -= 1
				rev = False
		st1 = st1 + st2
		if rev == True:
			st1 = reversed(st1)
		ans = ''
		for i in st1:
			if i != '@':
				ans = ans + i
		return ans


class Solution:

	def removeReverse(self, S):
		d = {}
		l = len(S) - 1
		for i in S:
			if i in d:
				d[i] += 1
			else:
				d[i] = 1
		lft = 0
		rht = l
		flag = False
		s1 = ''
		s2 = ''
		while lft <= rht:
			if flag == False:
				if d[S[lft]] > 1:
					d[S[lft]] -= 1
					s1 += '*'
					lft += 1
					flag = True
				else:
					s1 += S[lft]
					lft += 1
			elif d[S[rht]] > 1:
				d[S[rht]] -= 1
				s2 = '*' + s2
				rht -= 1
				flag = False
			else:
				s2 = S[rht] + s2
				rht -= 1
		s1 = s1 + s2
		ans = ''
		if flag == True:
			s1 = reversed(s1)
		for i in s1:
			if i != '*':
				ans += i
		return ans


class Solution:

	def removeReverse(self, s):
		d = {}
		n = len(s)
		for i in s:
			if i in d:
				d[i] += 1
			else:
				d[i] = 1
		i = 0
		j = n - 1
		k = -1
		while i < j:
			if n == 1:
				break
			while i < n and i < j and (d[s[i]] == 1):
				i += 1
			if i >= n - 1 or i >= j:
				break
			else:
				d[s[i]] -= 1
				s = s[0:i] + s[i + 1:]
				j -= 1
				n -= 1
			while j > i and j >= 0 and (d[s[j]] == 1):
				j -= 1
			if j <= 0 or j <= i:
				k = 0
				break
			else:
				k = -1
				d[s[j]] -= 1
				s = s[0:j] + s[j + 1:]
				n -= 1
				j -= 1
		if k == 0:
			s = s[-1::-1]
		return s


from collections import Counter

class Solution:

	def removeReverse(self, S):
		l = 0
		r = len(S) - 1
		rem = set()
		mp = Counter(list(S))
		while l <= r:
			while l <= r and mp[S[l]] == 1:
				l += 1
			if l <= r and mp[S[l]] > 1:
				mp[S[l]] -= 1
				rem.add(l)
				l += 1
			while l < r and mp[S[r]] == 1:
				r -= 1
			if l < r and mp[S[r]] > 1:
				mp[S[r]] -= 1
				rem.add(r)
				r -= 1
		ans = ''
		for i in range(len(S)):
			if i not in rem:
				ans += S[i]
		if len(rem) & 1:
			ans = ans[::-1]
		return ans


class Solution:

	def removeReverse(self, S):
		dic = {}
		for i in S:
			if i in dic:
				dic[i] += 1
			else:
				dic[i] = 1
		i = 0
		j = len(S) - 1
		d = 0
		S = list(S)
		while i < j:
			if d == 0:
				if dic[S[i]] == 1:
					i += 1
				else:
					dic[S[i]] -= 1
					S[i] = '@'
					d = 1
					i += 1
			if d == 1:
				if dic[S[j]] == 1:
					j -= 1
				else:
					dic[S[j]] -= 1
					S[j] = '@'
					d = 0
					j -= 1
		ans = ''
		for i in S:
			if i != '@':
				ans += i
		if d == 1:
			c = ''
			for i in reversed(ans):
				c += i
			return c
		return ans


from collections import Counter, deque

class Solution:

	def removeReverse(self, S):
		counter = Counter(S)
		left = 0
		forward = True
		right = len(S) - 1
		lstr = []
		rstr = []
		while left <= right:
			if forward:
				if counter[S[left]] == 1:
					lstr.append(S[left])
				else:
					forward = False
				counter[S[left]] -= 1
				left += 1
			else:
				if counter[S[right]] == 1:
					rstr.append(S[right])
				else:
					forward = True
				counter[S[right]] -= 1
				right -= 1
		if forward:
			return ''.join(lstr) + ''.join(rstr[::-1])
		else:
			return ''.join(rstr) + ''.join(lstr[::-1])


class Solution:

	def removeReverse(self, S):
		d = {}
		repeated = []
		for (i, c) in enumerate(S):
			if c not in d:
				d[c] = 0
			d[c] += 1
		for (i, c) in enumerate(S):
			if d[c] > 1:
				repeated.append(i)
		(i, j) = (0, len(repeated) - 1)
		f = 0
		removed = [0 for i in range(len(S))]
		while i <= j:
			if f == 0:
				idx = repeated[i]
				if d[S[idx]] > 1:
					d[S[idx]] -= 1
					removed[idx] = 1
					f = 1 - f
				i += 1
			else:
				idx = repeated[j]
				if d[S[idx]] > 1:
					d[S[idx]] -= 1
					removed[idx] = 1
					f = 1 - f
				j -= 1
		ans = [S[i] for i in range(len(S)) if removed[i] == 0]
		if f:
			ans = ans[::-1]
		return ''.join(ans)


from typing import List
from array import array

class Solution:

	def removeReverse(self, s: str) -> str:
		counter = array('I', [0] * 128)
		s_len = len(s)
		included = [True] * s_len
		for c in s:
			counter[ord(c)] += 1
		left = 0
		right = s_len - 1
		rev = False
		while left <= right:
			first = s[left]
			last = s[right]
			if not rev:
				if counter[ord(first)] > 1:
					counter[ord(first)] -= 1
					rev = not rev
					included[left] = False
				left += 1
			else:
				if counter[ord(last)] > 1:
					counter[ord(last)] -= 1
					rev = not rev
					included[right] = False
				right -= 1
		res = ''
		for i in range(s_len):
			if included[i]:
				res += s[i]
		if rev:
			res = res[::-1]
		return res


class Solution:

	def removeReverse(self, S):
		count = [0] * 26
		for i in S:
			count[ord(i) - 97] += 1
		left = 0
		right = len(S) - 1
		rev = False
		while left <= right:
			if rev:
				if count[ord(S[right]) - 97] > 1:
					count[ord(S[right]) - 97] -= 1
					rev = False
					S = S[:right] + S[right + 1:]
				right -= 1
			else:
				if count[ord(S[left]) - 97] > 1:
					count[ord(S[left]) - 97] -= 1
					rev = True
					S = S[:left] + S[left + 1:]
					left -= 1
					right -= 1
				left += 1
		if rev:
			return S[::-1]
		else:
			return S


class Solution:

	def removeReverse(self, S):
		K = 26
		N = len(S)
		dp = [0 for i in range(K)]
		mark = []
		for s in S:
			dp[ord(s) - ord('a')] += 1
			mark.append(1)
		c = len([i for i in dp if i > 1])
		(i, j) = (0, len(S) - 1)
		op = 1
		while c > 0:
			if op == 1:
				while i < j and dp[ord(S[i]) - ord('a')] <= 1:
					i += 1
				dp[ord(S[i]) - ord('a')] -= 1
				if dp[ord(S[i]) - ord('a')] == 1:
					c -= 1
				mark[i] = 0
				i += 1
				op = 0
			else:
				while i < j and dp[ord(S[j]) - ord('a')] <= 1:
					j -= 1
				dp[ord(S[j]) - ord('a')] -= 1
				if dp[ord(S[j]) - ord('a')] == 1:
					c -= 1
				mark[j] = 0
				j -= 1
				op = 1
		s = ''
		if op:
			for x in range(N):
				if mark[x]:
					s += S[x]
		else:
			for x in range(N - 1, -1, -1):
				if mark[x]:
					s += S[x]
		return s


class Solution:

	def removeReverse(self, S):
		d = {}
		for ch in S:
			if ch not in d:
				d[ch] = 1
			else:
				d[ch] += 1
		flag = 0
		st = 0
		ed = len(S) - 1
		while st <= ed:
			if flag == 0:
				if d[S[st]] == 1:
					st += 1
				else:
					d[S[st]] -= 1
					S = S[:st] + '#' + S[st + 1:]
					st += 1
					flag = 1
			elif d[S[ed]] == 1:
				ed -= 1
			else:
				d[S[ed]] -= 1
				S = S[:ed] + '#' + S[ed + 1:]
				ed -= 1
				flag = 0
		if flag == 1:
			S = S[::-1]
		S = S.replace('#', '')
		return S


class Solution:

	def removeReverse(self, S):
		dic = {}
		for s in S:
			dic[s] = dic.get(s, 0) + 1
		i = 0
		j = len(S) - 1
		cnt = 0
		con = True
		while j >= i:
			if con:
				if dic[S[i]] > 1:
					dic[S[i]] -= 1
					S = S[:i] + 'A' + S[i + 1:]
					i += 1
					con = not con
				else:
					i += 1
			elif dic[S[j]] > 1:
				dic[S[j]] -= 1
				S = S[:j] + 'A' + S[j + 1:]
				j -= 1
				con = not con
			else:
				j -= 1
		S = S.replace('A', '')
		if not con:
			S = S[::-1]
		return S


class Solution:

	def removeReverse(self, s):
		from collections import Counter
		cnt = Counter(s)
		(i, d) = (0, 1)
		while 0 <= i < len(s):
			if cnt[s[i]] > 1:
				cnt[s[i]] -= 1
				s = s[:i] + s[i + 1:]
				i = len(s) - 1 if d == 1 else 0
				d *= -1
			else:
				i += d
		return s if d > 0 else s[::-1]


class Solution:

	def removeReverse(self, S):
		d = 0
		S = list(S)
		dic = {}
		for i in S:
			if i not in dic.keys():
				dic[i] = 1
			else:
				dic[i] += 1
		s = 0
		e = len(S) - 1
		while s < e:
			if d == 0:
				if dic[S[s]] == 1:
					s += 1
				else:
					d = 1
					dic[S[s]] -= 1
					S[s] = 0
					s += 1
			elif dic[S[e]] == 1:
				e -= 1
			else:
				d = 0
				dic[S[e]] -= 1
				S[e] = 0
				e -= 1
		re = ''
		a = ''
		for i in S:
			if i != 0:
				re += i
		if d == 1:
			re = list(re)
			n = len(re)
			for i in range(n // 2):
				(re[i], re[n - i - 1]) = (re[n - 1 - i], re[i])
			for i in re:
				a += i
			re = a
		return re


from collections import defaultdict, Counter

class Pointer:

	def __init__(self, name, index, nxt_offset, end):
		self.name = name
		self._index = self._cur_index = index
		self._nxt_offset = nxt_offset
		self._end = end

	def reset(self):
		self._cur_index = self._index

	def has_next(self):
		return self._cur_index != self._end

	def next(self):
		if not self.has_next():
			raise StopIteration
		cur = self._cur_index
		self._cur_index += self._nxt_offset
		return cur

	def __str__(self):
		return self.name

class Pointer:

	def __init__(self, name, index, nxt_offset, end):
		self.name = name
		self._index = self._cur_index = index
		self._nxt_offset = nxt_offset
		self._end = end

	def reset(self):
		self._cur_index = self._index

	def has_next(self):
		return self._cur_index != self._end

	def next(self):
		if not self.has_next():
			raise StopIteration
		cur = self._cur_index
		self._cur_index += self._nxt_offset
		return cur

	def __str__(self):
		return self.name

class Solution:

	def removeReverse(self, s):
		n = len(s)
		(forward, backward) = (Pointer('forward', 0, 1, n), Pointer('backward', n - 1, -1, -1))
		char_counts = Counter(s)
		remove_indices = set()
		cur_ptr = forward
		while True:
			if not cur_ptr.has_next():
				break
			ind = cur_ptr.next()
			c = s[ind]
			if char_counts[c] > 1:
				char_counts[c] -= 1
				remove_indices.add(ind)
				cur_ptr = forward if cur_ptr == backward else backward
		ans = ''.join((c for (i, c) in enumerate(s) if i not in remove_indices))
		return ans if cur_ptr == forward else ans[::-1]


from collections import Counter

class Solution:

	def removeReverse(self, s):
		d = Counter(s)
		pos = {}
		n = len(s)
		i = 0
		j = n - 1
		rev = False
		while i <= j:
			if rev == False:
				if d[s[i]] > 1:
					d[s[i]] -= 1
					i += 1
					rev = True
				else:
					pos[i] = s[i]
					i += 1
			elif d[s[j]] > 1:
				d[s[j]] -= 1
				j -= 1
				rev = False
			else:
				pos[j] = s[j]
				j -= 1
		st = ''
		for i in range(n):
			if i in pos:
				st += pos[i]
		if rev == False:
			return st
		return st[::-1]


from collections import Counter

class Solution:

	def removeReverse(self, S):
		c = Counter(S)
		n = ''
		l = list(S)
		i = 0
		dir = 0
		j = len(l) - 1
		while i <= j:
			if dir == 0:
				if c[l[i]] > 1:
					c[l[i]] = c[l[i]] - 1
					l[i] = '@'
					dir = 1
				i = i + 1
			else:
				if c[l[j]] > 1:
					c[l[j]] = c[l[j]] - 1
					l[j] = '@'
					dir = 0
				j = j - 1
		for i in l:
			if i != '@':
				n += i
		if dir == 0:
			return n
		else:
			return n[::-1]


class Solution:

	def removeReverse(self, S):
		start = 0
		last = len(S) - 1
		dct = {}
		dct1 = {}
		front = 1
		for i in S:
			dct[i] = dct.get(i, 0) + 1
		while start <= last:
			if front:
				if dct[S[start]] > 1:
					dct[S[start]] -= 1
					front = 0
				else:
					dct1[start] = S[start]
				start += 1
			else:
				if dct[S[last]] > 1:
					dct[S[last]] -= 1
					front = 1
				else:
					dct1[last] = S[last]
				last -= 1
		ans = ''
		if front:
			for i in sorted(dct1.keys()):
				ans += dct1[i]
		else:
			for i in reversed(sorted(dct1.keys())):
				ans += dct1[i]
		return ans


class Solution:

	def removeReverse(self, S):
		rem = dict()
		h_map = dict()
		n = len(S)
		for i in range(0, n):
			if S[i] not in h_map:
				h_map[S[i]] = 0
			h_map[S[i]] += 1
		start = 0
		end = n - 1
		front = True
		while start < end:
			if front and h_map[S[start]] > 1:
				front = False
				rem[start] = 1
				h_map[S[start]] -= 1
				start += 1
			elif not front and h_map[S[end]] > 1:
				front = True
				rem[end] = 1
				h_map[S[end]] -= 1
				end -= 1
			elif front:
				start += 1
			else:
				end -= 1
		new_str = ''
		for i in range(0, n):
			if i not in rem:
				new_str += S[i]
		if front:
			return new_str
		else:
			return new_str[::-1]


class Solution:

	def removeReverse(self, S):
		s = list(S)
		freq = [0] * 26
		for ch in s:
			freq[ord(ch) - ord('a')] += 1
		(l, r) = (0, len(s) - 1)
		flag = 0
		while l <= r:
			if not flag:
				if freq[ord(s[l]) - ord('a')] == 1:
					l += 1
				else:
					freq[ord(s[l]) - ord('a')] -= 1
					s[l] = ''
					l += 1
					flag = not flag
			elif freq[ord(s[r]) - ord('a')] == 1:
				r -= 1
			else:
				freq[ord(s[r]) - ord('a')] -= 1
				s[r] = ''
				r -= 1
				flag = not flag
		if flag:
			s.reverse()
		return ''.join(s)


class Solution:

	def removeReverse(self, S):
		dict = {}
		for i in S:
			if i in dict:
				dict[i] += 1
			else:
				dict[i] = 1
		s = list(S)
		res = set(s)
		flag = 0
		index = 0
		while len(s) != len(res):
			if flag == 0:
				if dict[s[index]] > 1:
					dict[s[index]] -= 1
					del s[index]
					index = -1
					flag = 1
				else:
					index += 1
			elif dict[s[index]] > 1:
				dict[s[index]] -= 1
				del s[index]
				index = 0
				flag = 0
			else:
				index -= 1
		result = ''.join(s)
		if index < 0:
			return result[::-1]
		return result


from collections import Counter

class Solution:

	def removeReverse(self, s):
		s = list(s)
		counts = Counter(s)
		i = 0
		j = len(s) - 1
		flag = True
		while i <= j:
			if flag:
				if counts[s[i]] > 1:
					flag = not flag
					counts[s[i]] -= 1
					s[i] = None
				i += 1
			else:
				if counts[s[j]] > 1:
					flag = not flag
					counts[s[j]] -= 1
					s[j] = None
				j -= 1
		res = ''.join([i for i in s if i])
		return res if flag else res[::-1]


class Solution:

	def removeReverse(self, S):
		Y = []
		for i in S:
			Y.append(i)
		mp1 = {}
		for i in S:
			mp1[i] = mp1.get(i, 0) + 1
		i = 0
		j = len(Y) - 1
		d = 0
		while i <= j:
			if d == 0:
				if mp1[Y[i]] == 1:
					i += 1
				else:
					mp1[Y[i]] -= 1
					Y[i] = '5'
					i += 1
					d = 1
			elif mp1[Y[j]] == 1:
				j -= 1
			else:
				mp1[Y[j]] -= 1
				Y[j] = '5'
				j -= 1
				d = 0
		xy = ''
		for i in range(len(S)):
			if Y[i] != '5':
				xy += Y[i]
		if d == 1:
			xy = xy[::-1]
		return xy


class Solution:

	def removeReverse(self, S):
		d = {}
		for i in S:
			if i in d:
				d[i] += 1
			else:
				d[i] = 1
		return forward(S, 0, len(S) - 1, d)

def forward(S, i, j, d):
	cnt = 0
	beg = ''
	end = ''
	ans = ''
	flag = True
	(i, j) = (0, len(S) - 1)
	while i <= j:
		if flag:
			ch = S[i]
		else:
			ch = S[j]
		if d[ch] > 1:
			d[ch] -= 1
			cnt += 1
			if flag:
				flag = False
				i += 1
			else:
				flag = True
				j -= 1
		elif flag:
			beg += S[i]
			i += 1
		else:
			end = S[j] + end
			j -= 1
	ans = beg + end
	if cnt % 2 == 1:
		return ans[::-1]
	return ans


class Solution:

	def removeReverse(self, S):
		mp = {}
		for i in S:
			if i not in mp:
				mp[i] = 1
			else:
				mp[i] += 1
		S = list(S)
		flag = True
		(i, j) = (0, len(S) - 1)
		while i <= j:
			if flag:
				if mp[S[i]] > 1:
					mp[S[i]] -= 1
					S[i] = '0'
					flag = False
				i += 1
			else:
				if mp[S[j]] > 1:
					mp[S[j]] -= 1
					S[j] = '0'
					flag = True
				j -= 1
		ans = ''
		for i in S:
			if i != '0':
				ans += i
		if flag:
			return ans
		else:
			return ans[::-1]


class Solution:

	def removeReverse(self, S):
		freq_dict = self.findFreaquency(S)
		string_len = len(S)
		iterator_fwd = 0
		iterator_bkd = string_len - 1
		reverse_direction = 'fwd'
		while iterator_fwd != iterator_bkd:
			if reverse_direction == 'fwd':
				iterator = iterator_fwd
			else:
				iterator = iterator_bkd
			ch = S[iterator]
			if freq_dict[ch]['freq'] > 1:
				S = S[:iterator] + S[iterator + 1:]
				freq_dict[ch]['freq'] -= 1
				iterator_bkd -= 1
				reverse_direction = 'bkd' if reverse_direction == 'fwd' else 'fwd'
			elif reverse_direction == 'fwd':
				iterator_fwd += 1
			else:
				iterator_bkd -= 1
		return S if reverse_direction == 'fwd' else self.reverse_string(S)

	def findFreaquency(self, S):
		freq_object = {}
		for (index, char) in enumerate(S):
			if char in freq_object.keys():
				freq_object[char]['freq'] += 1
				freq_object[char]['index_list'].append(index)
			else:
				freq_object[char] = {'freq': 1, 'index_list': [index]}
		return freq_object

	def reverse_string(self, S):
		return S[::-1]


class Solution:

	def removeReverse(self, S):
		l = [S[i] for i in range(len(S))]
		from collections import defaultdict
		d = defaultdict(int)
		for i in l:
			d[i] += 1
		fg = 0
		i = 0
		while i >= 0 and i < len(l):
			f = 0
			if d[l[i]] > 1:
				d[l[i]] -= 1
				del l[i]
				fg = (fg + 1) % 2
				f = 1
			if f == 1:
				if fg == 0:
					i = 0
				else:
					i = len(l) - 1
			elif fg == 0:
				i += 1
			else:
				i -= 1
		s = ''
		if fg == 1:
			l = l[::-1]
		for i in l:
			s += i
		return s


class Solution:

	def removeReverse(self, s):
		l = len(s)
		s = list(s)
		m = {}
		for c in s:
			if c not in m:
				m[c] = 1
			else:
				m[c] += 1
		(i, j) = (0, l - 1)
		while i <= j:
			while i < len(s) and m[s[i]] == 1:
				i += 1
			if i < len(s):
				m[s[i]] -= 1
				s.pop(i)
				j -= 1
			while j >= 0 and m[s[j]] == 1:
				j -= 1
			if j >= 0:
				m[s[j]] -= 1
				s.pop(j)
				j -= 1
		if (l - len(s)) % 2 == 0:
			return ''.join(s)
		else:
			return ''.join(s[::-1])


from collections import deque, Counter

class Solution:

	def removeReverse(self, S):
		a = []
		b = []
		(i, j) = (0, len(S) - 1)
		flag = 0
		c = Counter(S)
		while i <= j:
			if flag == 0:
				if c[S[i]] > 1:
					c[S[i]] -= 1
					flag = 1
				else:
					a.append(S[i])
				i += 1
			else:
				if c[S[j]] > 1:
					c[S[j]] -= 1
					flag = 0
				else:
					b.append(S[j])
				j -= 1
		b.reverse()
		s = ''
		for i in a:
			s += i
		for i in b:
			s += i
		if flag:
			s = s[::-1]
		return s


from collections import defaultdict

class Solution:

	def removeReverse(self, S):
		(l, r) = (0, len(S) - 1)
		rev = False
		charFreq = [0] * 26
		for i in range(len(S)):
			charFreq[ord(S[i]) - ord('a')] += 1
		removed = [0] * len(S)
		while l <= r:
			if rev:
				if charFreq[ord(S[r]) - ord('a')] > 1:
					charFreq[ord(S[r]) - ord('a')] -= 1
					rev = False
				else:
					removed[r] = 1
				r -= 1
			else:
				if charFreq[ord(S[l]) - ord('a')] > 1:
					charFreq[ord(S[l]) - ord('a')] -= 1
					rev = True
				else:
					removed[l] = 1
				l += 1
		ans = ''
		for i in range(len(S)):
			if removed[i] == 1:
				ans += S[i]
		return ans[::-1] if rev else ans


class Solution:

	def removeReverse(self, s):
		r = []
		l = [0] * 26
		for i in s:
			l[ord(i) % 97] = l[ord(i) % 97] + 1
		end = len(s) - 1
		start = 0
		d = 0
		while end != start:
			if d == 0:
				if l[ord(s[start]) % 97] > 1:
					r.append(start)
					l[ord(s[start]) % 97] = l[ord(s[start]) % 97] - 1
					d = 1
				start = start + 1
			else:
				if l[ord(s[end]) % 97] > 1:
					r.append(end)
					l[ord(s[end]) % 97] = l[ord(s[end]) % 97] - 1
					d = 0
				end = end - 1
		s = list(s)
		r = sorted(r)[::-1]
		for i in r:
			s.pop(i)
		st = ''
		for i in s:
			st = st + i
		if d == 0:
			return st
		return st[::-1]


from collections import *

class Solution:

	def removeReverse(self, S):
		S = list(S)
		d = Counter(S)
		n = len(S)
		k = 0
		i = 0
		j = len(S) - 1
		while i <= j:
			if k == 0:
				while i < n:
					if d[S[i]] > 1:
						d[S[i]] -= 1
						S[i] = '$'
						break
					i += 1
				k = 1 - k
			else:
				while j >= 0:
					if d[S[j]] > 1:
						d[S[j]] -= 1
						S[j] = '$'
						break
					j -= 1
				k = 1 - k
		s = ''
		if k:
			for i in S:
				if i == '$':
					continue
				else:
					s += i
		else:
			for i in S[::-1]:
				if i == '$':
					continue
				else:
					s += i
		return s


from typing import List
from array import array

class Solution:

	def removeReverse(self, s: str) -> str:
		ctr = array('I', [0] * 128)
		s_len = len(s)
		included = [True] * s_len
		for c in s:
			ctr[ord(c)] += 1
		l = 0
		r = s_len - 1
		rev = False
		while l <= r:
			f = s[l]
			lst = s[r]
			if not rev:
				if ctr[ord(f)] > 1:
					ctr[ord(f)] -= 1
					rev = not rev
					included[l] = False
				l += 1
			else:
				if ctr[ord(lst)] > 1:
					ctr[ord(lst)] -= 1
					rev = not rev
					included[r] = False
				r -= 1
		res = ''
		for i in range(s_len):
			if included[i]:
				res += s[i]
		if rev:
			res = res[::-1]
		return res


class Solution:

	def removeReverse(self, x):

		def dmax(d):
			m = 0
			for p in d:
				if d[p] > m:
					m = d[p]
			return m
		S = [p for p in x]
		d = {}
		for i in range(len(S)):
			if S[i] not in d:
				d[S[i]] = 1
			else:
				d[S[i]] += 1
		k = 0
		while 1:
			for i in range(len(S)):
				if d[S[i]] > 1:
					d[S[i]] -= 1
					S.pop(i)
					k += 1
					break
			if dmax(d) == 1:
				if k % 2:
					return ''.join(S)[::-1]
				else:
					return ''.join(S)
			for i in range(len(S) - 1, -1, -1):
				if d[S[i]] > 1:
					d[S[i]] -= 1
					S.pop(i)
					k += 1
					break
			if dmax(d) == 1:
				if k % 2:
					return ''.join(S)[::-1]
				else:
					return ''.join(S)


class Solution:

	def removeReverse(self, S):
		ans = ''
		n = len(S)
		q = set()
		m = {}
		p = {}
		for i in range(n):
			if S[i] not in m:
				m[S[i]] = 0
			m[S[i]] += 1
			p[i] = 1
		i = 0
		j = n - 1
		k = i
		r = 0
		while i < n and j >= 0 and (i <= j):
			if m[S[k]] > 1:
				m[S[k]] -= 1
				p[k] = 0
				if r:
					j -= 1
					k = i
					r = 0
				else:
					i += 1
					k = j
					r = 1
			elif r:
				k -= 1
				j -= 1
			else:
				i += 1
				k += 1
		for i in range(n):
			if p[i] > 0:
				ans += S[i]
		if r:
			ans = ans[::-1]
		return ans


class Solution:

	def removeReverse(self, S):
		dic = {}
		for c in S:
			if c not in dic:
				dic[c] = 1
			else:
				dic[c] += 1
		i = 0
		d = 1
		while 0 <= i < len(S):
			if dic[S[i]] > 1:
				dic[S[i]] -= 1
				S = S[:i] + S[i + 1:]
				if d == 1:
					i = len(S) - 1
				else:
					i = 0
				d *= -1
			else:
				i += d
		return S if d > 0 else S[::-1]


class Solution:

	def removeReverse(self, s):
		n = len(s)
		count = dict()
		for i in range(len(s)):
			count[s[i]] = count.get(s[i], 0) + 1
		chars_size = len(count)
		sens = 1
		while chars_size < n:
			for i in range((n - 1) * (1 - sens) // 2, n * (1 + sens) // 2 - (1 - sens) // 2, sens):
				if count[s[i]] > 1:
					count[s[i]] = count[s[i]] - 1
					s = s[:i] + s[i + 1:]
					n = n - 1
					sens = -sens
					break
		final_chars = ''
		for i in range((n - 1) * (1 - sens) // 2, n * (1 + sens) // 2 - (1 - sens) // 2, sens):
			final_chars = final_chars + s[i]
		return final_chars


class Solution:

	def removeReverse(self, S):
		dic = {}
		n = len(S)
		s = list(S)
		for i in S:
			if i in dic:
				dic[i] += 1
			else:
				dic[i] = 1
		i = 0
		j = n - 1
		dir = 1
		while i <= j:
			if dir == 1:
				if dic[S[i]] == 1:
					i += 1
				else:
					dic[S[i]] -= 1
					s[i] = '@'
					i += 1
					dir = -1
			elif dic[S[j]] == 1:
				j -= 1
			else:
				dic[S[j]] -= 1
				s[j] = '@'
				j -= 1
				dir = 1
		ans = ''
		for i in s:
			if i != '@':
				ans = ans + i
		if dir == -1:
			return ans[::-1]
		return ans