You are given a string s of lower case english alphabets. You can choose any two characters in the string and replace all the occurences of the first character with the second character and replace all the occurences of the second character with the first character. Your aim is to find the lexicographically smallest string that can be obtained by doing this operation at most once.
Example 1:
Input:
A = "ccad"
Output: "aacd"
Explanation:
In ccad, we choose a and c and after 
doing the replacement operation once we get, 
aacd and this is the lexicographically
smallest string possible. 
 
Example 2:
Input:
A = "abba"
Output: "abba"
Explanation:
In abba, we can get baab after doing the 
replacement operation once for a and b 
but that is not lexicographically smaller 
than abba. So, the answer is abba. 
Your Task:  
You don't need to read input or print anything. Your task is to complete the function chooseandswap() which takes the string A as input parameters and returns the lexicographically smallest string that is possible after doing the operation at most once.
Expected Time Complexity: O(|A|) length of the string A
Expected Auxiliary Space: O(1)
 
Constraints:
1<= |A| <=10^{5}

Source: geeksforgeeks | Difficulty: EASY
Tags: Greedy algorithms

Starter code: #User function Template for python3





class Solution:

    def chooseandswap (self, A):

        # code here

        pass







Solutions:
class Solution:

	def chooseandswap(self, a):
		arr = list(A)
		freq = [0] * 26
		for c in arr:
			freq[ord(c) - ord('a')] += 1
		for i in range(len(arr)):
			curr = arr[i]
			for j in range(ord(curr) - ord('a')):
				if freq[j] > 0:
					return self.replace(arr, curr, chr(ord('a') + j))
			freq[ord(curr) - ord('a')] = 0
		return A

	def replace(self, arr, a, b):
		for i in range(len(arr)):
			if arr[i] == a:
				arr[i] = b
			elif arr[i] == b:
				arr[i] = a
		return ''.join(arr)


class Solution:

	def chooseandswap(self, A):
		d = {}
		for letter in A:
			d[letter] = True
		for letter in A:
			for char in [chr(l) for l in range(ord('a'), ord(letter))]:
				if char in d and d[char]:
					A = A.replace(letter, '*')
					A = A.replace(char, letter)
					A = A.replace('*', char)
					return A
			d[letter] = False
		return A


class Solution:

	def chooseandswap(self, A):
		dct = {}
		for ch in A:
			dct[ch] = True
		for ch in A:
			for char in [chr(l) for l in range(ord('a'), ord(ch))]:
				if char in dct and dct[char]:
					A = A.replace(ch, '*')
					A = A.replace(char, ch)
					A = A.replace('*', char)
					return A
			dct[ch] = False
		return A


class Solution:

	def chooseandswap(self, A):
		chars = list(A)
		unique_chars = sorted(set(chars))
		i = 0
		for ch in chars:
			if unique_chars[i] < ch:
				A = A.replace(ch, '1').replace(unique_chars[i], '2')
				A = A.replace('1', unique_chars[i]).replace('2', ch)
				break
			elif unique_chars[i] == ch:
				i += 1
				if i == len(unique_chars):
					break
		return A


class Solution:

	def chooseandswap(self, A):
		char_array = [-1] * 26
		j = 0
		for i in range(len(A)):
			if char_array[ord(A[i]) - ord('a')] == -1:
				char_array[ord(A[i]) - ord('a')] = i
		for i in range(len(A)):
			flag = 0
			for j in range(ord(A[i]) - ord('a') + 1):
				if char_array[j] > char_array[ord(A[i]) - ord('a')]:
					flag = 1
					break
			if flag == 1:
				break
		s = ''
		if i < len(A):
			c = A[i]
			c2 = chr(j + ord('a'))
			for i in range(len(A)):
				if A[i] == c:
					s += c2
				elif A[i] == c2:
					s += c
				else:
					s += A[i]
			return s


class Solution:

	def chooseandswap(self, a):
		toReplace = ''
		replaceWith = ''
		m = [0 for x in range(26)]
		for x in a:
			m[ord(x) - ord('a')] += 1
		for x in a:
			for y in range(26):
				if m[y] and ord(x) - ord('a') > y:
					toReplace = x
					replaceWith = y
					break
			if toReplace != '':
				break
			else:
				m[ord(x) - ord('a')] = 0
		a = list(a)
		if toReplace != '' and replaceWith != '':
			for x in range(len(a)):
				if a[x] == toReplace:
					a[x] = chr(ord('a') + replaceWith)
				elif a[x] == chr(ord('a') + replaceWith):
					a[x] = toReplace
		return ''.join(a)


from collections import OrderedDict

class Solution:

	def chooseandswap(self, A):
		n = len(A)
		data = OrderedDict()
		data1 = []
		for i in range(n):
			if A[i] not in data:
				data[A[i]] = ord(A[i])
				data1.append([ord(A[i]), i])
		swap = None
		ind = None
		for j in range(1, len(data1)):
			if data1[j - 1][0] > data1[j][0]:
				swap = data1[j - 1]
				ind = j - 1
				break
		if swap == None:
			return A
		min_ord = swap[0]
		for k in range(ind + 1, len(data1)):
			min_ord = min(min_ord, data1[k][0])
		if min_ord == swap[0]:
			return A
		max_ord = None
		for k in range(0, ind + 1):
			if data1[k][0] > min_ord:
				max_ord = data1[k][0]
				break
		(p, q) = (chr(max_ord), chr(min_ord))
		res = ''
		for each in A:
			if each == p:
				res += q
			elif each == q:
				res += p
			else:
				res += each
		return res
		abaebbbfsefbfgdcwgwragrgraweawqaaqwqdefvyqefaa
		abacbbbfscfbfgdewgwragrgrawcawqaaqwqdcfvyqcfaa
		abaebbbfqefbfgdcwgwragrgraweawsaaswsdefvysefaa
		abaebbbfsefbfgdcwgwragrgraweawqaaqwqdefvyqefaa
		[('a', 1), ('b', 1), ('e', 1), ('f', 1), ('s', 1), ('g', 1), ('d', 1), ('c', 1), ('w', 1), ('r', 1), ('q', 1), ('v', 1), ('y', 1)]
		abaebbbfsefbfgdcwgwragrgraweawqaaqwqdefvyqefaa
		abaebbbfqefbfgdcwgwragrgraweawsaaswsdefvysefaa


class Solution:

	def chooseandswap(self, A):
		d = {}
		for i in range(len(A)):
			if ord(A[i]) - 97 not in d:
				d[ord(A[i]) - 97] = i
			if len(d) == 26:
				break
		prev = 0
		flag = 1
		replace = -1
		replace_with = None
		for i in range(26):
			if i in d:
				if d[i] < prev and flag == 1:
					replace = prev
					flag = 0
				if d[i] < replace and flag == 0:
					replace = d[i]
				prev = d[i]
		for i in range(26):
			if i in d:
				if d[i] > replace:
					replace_with = d[i]
					break
		if replace != -1 and replace_with != None:
			a = A[replace]
			b = A[replace_with]
			A = A.replace(a, '1')
			A = A.replace(b, a)
			A = A.replace('1', b)
		return A


class Solution:

	def chooseandswap(self, A):
		arr = list(A)
		unique_chars = list(set(arr))
		unique_chars.sort()
		for ch in arr:
			if ch in unique_chars:
				unique_chars.remove(ch)
				if len(unique_chars) == 0:
					break
			chr = unique_chars[0]
			if ch > chr:
				for i in range(len(arr)):
					if arr[i] == ch:
						arr[i] = chr
					elif arr[i] == chr:
						arr[i] = ch
				break
		return ''.join(arr)


class Solution:

	def chooseandswap(self, A):
		string = list(A)
		loc = [-1] * 26
		for (i, c) in enumerate(string):
			idx = ord(c) - 97
			if loc[idx] == -1:
				loc[idx] = i
		for (i, c) in enumerate(string):
			found = False
			for j in range(ord(c) - 97):
				if loc[j] > loc[ord(c) - 97]:
					found = True
					break
			if found:
				break
		if i < len(string) - 1:
			(c1, c2) = (string[i], chr(j + 97))
			for (i, c) in enumerate(string):
				if c == c1:
					string[i] = c2
				elif c == c2:
					string[i] = c1
		ans = ''.join(string)
		return ans


class Solution:

	def chooseandswap(self, A):
		i = 0
		visited = set()
		while i < len(A):
			first = A[i]
			to_val = A[i]
			visited.add(A[i])
			for j in range(i + 1, len(A)):
				if ord(A[j]) < ord(to_val) and A[j] not in visited:
					to_val = A[j]
			if to_val == A[i]:
				i += 1
			else:
				A = list(A)
				for i in range(len(A)):
					if A[i] == first:
						A[i] = to_val
					elif A[i] == to_val:
						A[i] = first
				return ''.join(A)
		return A


class Solution:

	def chooseandswap(self, A):
		d = {}
		s = []
		for x in A:
			d[x] = False
			s.append(x)
		i = 0
		flag = False
		while i < len(A):
			var = None
			j = i + 1
			while j < len(A):
				if not d[A[j]]:
					if var == None and A[j] != A[i]:
						var = A[j]
					elif var != None and A[j] < var:
						var = A[j]
				j += 1
			if var and var < A[i]:
				flag = True
				break
			d[A[i]] = True
			i += 1
		if flag:
			sub = ''
			for x in A:
				if x == var:
					sub += A[i]
				elif x == A[i]:
					sub += var
				else:
					sub += x
			return sub
		return A


class Solution:

	def chooseandswap(self, A):
		temp = []
		for i in A:
			if i not in temp:
				temp.append(i)
		temp2 = sorted(temp)
		i = 0
		while i < len(temp) - 1 and temp[i] == temp2[i]:
			i += 1
		start = temp[i]
		minw = temp2[i]
		ans = []
		for i in list(A):
			if i == start:
				ans.append(minw)
			elif i == minw:
				ans.append(start)
			else:
				ans.append(i)
		return ''.join(ans)


class Solution:

	def findMin(self, A):
		min1 = 'z'
		cnt = 0
		for i in range(len(A)):
			if min1 > A[i]:
				(min1, cnt) = (A[i], i)
		return (min1, cnt)

	def chooseandswap(self, A):
		d = {}
		for letter in A:
			d[letter] = True
		for letter in A:
			for char in [chr(l) for l in range(ord('a'), ord(letter))]:
				if char in d and d[char]:
					A = A.replace(letter, '#')
					A = A.replace(char, letter)
					A = A.replace('#', char)
					return A
			d[letter] = False
		return A
		min1 = 'z'
		min2 = 'z'
		cnt = 0
		prev = 'b'
		i = 0
		j = len(A) - 1
		visited = set()
		(min1, cnt) = self.findMin(A)
		for i in range(len(A) - 1):
			(min1, cnt) = self.findMin(A[i:])
			visited.add(min1)
			if A[i] > min1 and min1 not in visited:
				print(A[i])
				print(visited)
				min2 = A[i]
				A = A.replace(min1, '#')
				A = A.replace(min2, min1)
				A = A.replace('#', min2)
				return A
		if A[0] == min1:
			return A
		visited = set()
		return A


class Solution:

	def chooseandswap(self, A):
		seen = [False] * 26
		a = ord('a')
		for c in A:
			seen[ord(c) - a] = True
		cur = 0
		to_replace = None
		for (i, c) in enumerate(A):
			while cur < 26 and (not seen[cur]):
				cur += 1
			if ord(c) - a > cur:
				to_replace = c
				break
			elif ord(c) - a == cur:
				cur += 1
		if to_replace and cur < 26:
			res = []
			from_replace = chr(cur + a)
			for c in A:
				if c == to_replace:
					res.append(from_replace)
				elif c == from_replace:
					res.append(to_replace)
				else:
					res.append(c)
			return ''.join(res)
		return A


class Solution:

	def chooseandswap(self, str):
		n = len(str)
		str = list(str)
		(i, j) = (0, 0)
		chk = [0 for i in range(256)]
		for i in range(256):
			chk[i] = -1
		for i in range(n):
			if chk[ord(str[i])] == -1:
				chk[ord(str[i])] = i
		for i in range(n):
			flag = False
			for j in range(ord(str[i])):
				if chk[j] > chk[ord(str[i])]:
					flag = True
					break
			if flag:
				break
		if i < n - 1:
			ch1 = str[i]
			ch2 = chr(j)
			for i in range(n):
				if str[i] == ch1:
					str[i] = ch2
				elif str[i] == ch2:
					str[i] = ch1
		return ''.join(str)


class Solution:

	def chooseandswap(self, A):
		d = {}
		for i in A:
			d[i] = True
		for i in A:
			for j in [chr(m) for m in range(ord('a'), ord(i))]:
				if j in d and d[j]:
					A = A.replace(i, '*')
					A = A.replace(j, i)
					A = A.replace('*', j)
					return A
			d[i] = False
		return A


class Solution:

	def chooseandswap(self, str):
		new = list(str)
		a = list(set(str))
		a.sort(reverse=True)
		for x in new:
			if x in a:
				if x == a[-1]:
					a.pop()
				else:
					(item, repwith) = (x, a[-1])
					break
		else:
			return str
		for (y, x) in enumerate(new):
			if x == item:
				new[y] = repwith
			elif x == repwith:
				new[y] = item
		return ''.join(new)


class Solution:

	def chooseandswap(self, a):
		x = list(a)
		lex = sorted(list(set(x)), reverse=True)
		(corr, t) = ('', 1)
		for (p, q) in enumerate(x):
			if q in lex and t:
				if q == lex[-1]:
					lex.pop()
				else:
					(corr, wrong) = (lex[-1], q)
					t = 0
			if corr:
				if q == wrong:
					x[p] = corr
				elif q == corr:
					x[p] = wrong
		return ''.join(x)


class Solution:

	def chooseandswap(self, arr):
		visited = set()
		for ele in arr:
			visited.add(ele)
		sarr = sorted(list(visited))
		curr = 0
		swap = None
		for (let, char) in enumerate(arr):
			if curr == len(sarr) - 1:
				break
			if char <= sarr[curr]:
				if char in visited:
					visited.remove(char)
					curr += 1
			else:
				swap = char
				break
		if swap:
			arr = list(arr)
			for (i, ele) in enumerate(arr):
				if ele == swap:
					arr[i] = sarr[curr]
				elif ele == sarr[curr]:
					arr[i] = swap
			arr = ''.join(arr)
		return arr


class Solution:

	def swap(self, A, x, y):
		for i in range(len(A)):
			if A[i] == x:
				A = A[:i] + y + A[i + 1:]
			elif A[i] == y:
				A = A[:i] + x + A[i + 1:]
		return A

	def chooseandswap(self, A):
		setData = set(A)
		for x in A:
			setData.discard(x)
			for val in range(ord('a'), ord(x)):
				if chr(val) in setData:
					return self.swap(A, x, chr(val))
		return A


class Solution:

	def chooseandswap(self, A):
		char = [-1] * 26
		for i in range(len(A)):
			if char[ord(A[i]) - ord('a')] == -1:
				char[ord(A[i]) - ord('a')] = i
		for i in range(len(A)):
			flag = False
			for j in range(ord(A[i]) - ord('a')):
				if char[j] > char[ord(A[i]) - ord('a')]:
					flag = True
					break
			if flag:
				break
		if i >= len(A) - 1:
			return A
		s1 = A[i]
		s2 = A[char[j]]
		res = ''
		for i in A:
			if i != s1 and i != s2:
				res += i
			elif i == s1:
				res += s2
			else:
				res += s1
		return res


import string

class Solution:

	def chooseandswap(self, A):
		x = None
		y = None
		l = list(set(A))
		l.sort()
		for i in A:
			if i in l:
				l.remove(i)
			if l and l[0] < i:
				x = l[0]
				y = i
				break
		s = ''
		for i in A:
			if i == x:
				s += y
			elif i == y:
				s += x
			else:
				s += i
		return s


class Solution:

	def chooseandswap(self, A):
		srt = sorted(set(A), reverse=True)
		pool = set()
		for item in A:
			if srt and item == srt[-1]:
				pool.add(srt.pop())
			elif item not in pool:
				result = ''
				for char in A:
					if char == item:
						result += srt[-1]
					elif char == srt[-1]:
						result += item
					else:
						result += char
				return result
		return A


class Solution:

	def chooseandswap(self, A):
		b = ''.join(sorted(A))
		if A == b:
			return A
		d = dict()
		for i in range(len(A)):
			if A[i] not in d:
				d[A[i]] = i
		ans = ''
		while len(d) > 0:
			m = min(d)
			for i in range(d[m]):
				if A[i] > m:
					n = A[i]
					for i in range(len(A)):
						if A[i] != n and A[i] != m:
							ans += A[i]
						elif A[i] == n:
							ans += m
						elif A[i] == m:
							ans += n
					return ans
			d.pop(m)
		return A


class Solution:

	def chooseandswap(self, A):
		d = {}
		l = []
		ls = []
		for i in A:
			if i not in d:
				l.append(i)
				ls.append(i)
				d[i] = i
		ls.sort()
		sp1 = ''
		sp2 = ''
		for i in range(len(ls)):
			if ls[i] != l[i]:
				sp1 = ls[i]
				sp2 = l[i]
				break
		res = ''
		for i in A:
			if i == sp1:
				res += sp2
			elif i == sp2:
				res += sp1
			else:
				res += i
		return res


class Solution:

	def chooseandswap(self, s):
		s = list(s)
		n = len(s)
		mapping = [c for c in 'abcdefghijklmnopqrstuvwxyz']
		f = [0] * 26
		for i in s:
			f[ord(i) - 97] += 1
		for i in range(n):
			index = ord(s[i]) - 97
			found = False
			for j in range(index):
				if f[j]:
					mapping[index] = chr(j + 97)
					mapping[j] = s[i]
					found = True
					break
			f[index] = 0
			if found:
				break
		for i in range(n):
			s[i] = mapping[ord(s[i]) - 97]
		return ''.join(s)


class Solution:

	def chooseandswap(self, A):
		if len(A) <= 1:
			return A
		s = []
		for i in A:
			if i not in s:
				s.append(i)
		s.sort()
		for i in A:
			if i in s:
				s.remove(i)
			if not s:
				return A
			ch = s[0]
			if i > ch:
				for j in range(len(A)):
					if A[j] == i:
						A = A[:j] + ch + A[j + 1:]
					elif A[j] == ch:
						A = A[:j] + i + A[j + 1:]
				return A


class Solution:

	def chooseandswap(self, A):
		s_a = list(set(A))
		s_a.sort()
		j = 0
		ans = None

		def swap(A, a, b):
			l = list(A)
			d = {a: [], b: []}
			for i in range(len(l)):
				if l[i] == a:
					d[a].append(i)
				if l[i] == b:
					d[b].append(i)
			for i in d[a]:
				l[i] = b
			for i in d[b]:
				l[i] = a
			return ''.join(l)
		for i in range(len(A)):
			if j > len(s_a) - 1:
				break
			if s_a[j] < A[i]:
				ans = swap(A, s_a[j], A[i])
				break
			if s_a[j] == A[i]:
				j += 1
		return ans if ans != None else A


class Solution:

	def chooseandswap(self, A):
		s = set(list(A))
		for i in range(len(A)):
			if A[i] in s:
				s.remove(A[i])
			if len(s) == 0:
				return A
			if min(s) < A[i]:
				temp = A[i]
				A = A.replace(A[i], '$')
				A = A.replace(min(s), temp)
				A = A.replace('$', min(s))
				break
		return A


class Solution:

	def chooseandswap(self, s):
		t = sorted(set(s))
		for i in range(len(s)):
			if s[i] in t:
				t.remove(s[i])
			if len(t) == 0:
				break
			if t[0] < s[i]:
				temp = s[i]
				for i in range(len(s)):
					if s[i] == temp:
						s = s[:i] + t[0] + s[i + 1:]
					elif s[i] == t[0]:
						s = s[:i] + temp + s[i + 1:]
				break
		return s


class Solution:

	def chooseandswap(self, A):
		s = set(list(A))
		i = 0
		while i < len(A):
			if A[i] in s:
				s.remove(A[i])
			if len(s) == 0:
				return A
			min_ = min(s)
			if min_ < A[i]:
				temp = A[i]
				A = A.replace(temp, '*')
				A = A.replace(min_, temp)
				A = A.replace('*', min_)
				return A
			else:
				i += 1


class Solution:

	def chooseandswap(self, A):
		l = list(set(A))
		l.sort()
		B = A
		mini = A
		for i in range(len(l)):
			for j in range(i + 1, len(l)):
				B = B.replace(l[i], '*')
				B = B.replace(l[j], l[i])
				B = B.replace('*', l[j])
				if B < mini:
					mini = B
				B = A
		return mini


class Solution:

	def chooseandswap(self, A):
		l = [-1 for i in range(26)]
		for i in range(len(A)):
			if l[ord(A[i]) - 97] == -1:
				l[ord(A[i]) - 97] = i
		a = ''
		b = ''
		for i in range(len(A)):
			for j in range(ord(A[i]) - 97):
				if l[j] > l[ord(A[i]) - 97]:
					a = A[l[j]]
					b = A[l[ord(A[i]) - 97]]
					break
			if a != '' and b != '':
				break
		A = list(A)
		for i in range(len(A)):
			if A[i] == a:
				A[i] = b
			elif A[i] == b:
				A[i] = a
		return ''.join(A)


class Solution:

	def chooseandswap(self, A):
		s = list(set(A))
		s.sort()
		for smallestchar in s:
			smallestpos = A.index(smallestchar)
			found = False
			for ch in A:
				if ch > smallestchar:
					found = True
					break
			if not found:
				continue
			biggerpos = A.index(ch)
			if biggerpos < smallestpos:
				A = A.replace(ch, '#')
				A = A.replace(smallestchar, ch)
				A = A.replace('#', smallestchar)
				return A
		return A
		pass


class Solution:

	def chooseandswap(self, A):
		i = ord('a')
		dict = {}
		while i <= ord('z'):
			if dict.get(i, -2) == -2:
				dict[i] = -1
			i += 1
		for (i, val) in enumerate(A):
			if dict.get(ord(val)) == -1:
				dict[ord(val)] = i
		flag = False
		(c1, c2) = (None, None)
		j = ord('a')
		for i in A:
			j = ord('a')
			while j < ord(i):
				if dict[j] > dict[ord(i)]:
					flag = True
					c1 = chr(j)
					break
				j += 1
			if flag:
				c2 = i
				break
		A = list(A)
		for (i, val) in enumerate(A):
			if val == c1:
				A[i] = c2
			if val == c2:
				A[i] = c1
		return ''.join(A)


class Solution:

	def chooseandswap(self, a):
		l = [-1] * 26
		n = len(a)
		(p, q) = ('', '')
		for i in range(n):
			x = ord(a[i]) - 97
			if l[x] == -1:
				l[x] = i
		for i in a:
			x = ord(i) - 97
			f = False
			for j in range(x):
				if l[j] > l[x]:
					p = a[l[j]]
					q = i
					f = True
					break
			if f:
				break
		if f:
			a = a.replace(p, '#')
			a = a.replace(q, p)
			a = a.replace('#', q)
		return a


class Solution:

	def chooseandswap(self, A):
		occ = set()
		for i in A:
			occ.add(ord(i) - 97)
		occ = list(occ)
		ans = ''
		present = []
		toChange = []
		found = False
		for i in A:
			mn = 100
			temp = ord(i) - 97
			for j in occ:
				if j < temp and j < mn and (chr(j + 97) not in present):
					toChange = [i, chr(j + 97)]
					mn = j
					found = True
			present.append(i)
			if found:
				break
		if found:
			for i in A:
				if i == toChange[0]:
					ans += toChange[1]
				elif i == toChange[1]:
					ans += toChange[0]
				else:
					ans += i
			return ans
		return A


class Solution:

	def chooseandswap(self, A):
		set1 = set()
		smallest = None
		i = 0
		while i < len(A):
			j = i + 1
			set1.add(A[i])
			smallest = None
			while j < len(A):
				if A[j] not in set1 and A[i] > A[j]:
					if smallest == None:
						smallest = A[j]
					elif smallest > A[j]:
						smallest = A[j]
				j += 1
			if smallest != None:
				break
			i += 1
		if smallest == None:
			return A
		else:
			largest = A[i]
			ans = ''
			for ele in A:
				if ele == largest:
					ans += smallest
				elif ele == smallest:
					ans += largest
				else:
					ans += ele
			return ans


class Solution:

	def chooseandswap(self, A):
		a = [0] * 26
		B = ''
		for i in range(len(A)):
			if a[ord(A[i]) - ord('a')] == 0:
				a[ord(A[i]) - ord('a')] = i + 1
				B += A[i]
		intial = 0
		(smallest, largest) = (A[0], A[0])
		for i in range(len(a)):
			if a[i] != 0 and a[i] != intial + 1 and (chr(i + ord('a')) != B[intial]):
				smallest = B[intial]
				largest = chr(i + ord('a'))
				break
			elif a[i] != 0:
				intial += 1
		A = A.replace(smallest, '!')
		A = A.replace(largest, smallest)
		A = A.replace('!', largest)
		return A


class Solution:

	def chooseandswap(self, A):
		st = sorted(set(A))
		a = list(A)
		for i in range(len(a)):
			if a[i] in st:
				st.remove(a[i])
			if st and st[0] < a[i]:
				x = st[0]
				y = a[i]
				for j in range(len(a)):
					if a[j] == x:
						a[j] = y
					elif a[j] == y:
						a[j] = x
				return ''.join(a)
		return ''.join(a)


class Solution:

	def chooseandswap(self, A):

		def swap(e, x, y):
			if e == x:
				return y
			if e == y:
				return x
			return e
		s = set(A)
		for e in A:
			for p in [chr(v) for v in range(ord('a'), ord(e))]:
				if p in s:
					return ''.join((swap(x, p, e) for x in A))
			s.discard(e)
		return A


from collections import Counter

class Solution:

	def chooseandswap(self, A):
		n = len(A)
		A = [i for i in A]
		(i, j) = (0, 0)
		chk = [-1 for i in range(256)]
		for i in range(n):
			if chk[ord(A[i])] == -1:
				chk[ord(A[i])] = i
		for i in range(n):
			flag = False
			for j in range(ord(A[i])):
				if chk[j] > chk[ord(A[i])]:
					flag = True
					break
			if flag:
				break
		if i < n - 1:
			s = ''
			ch1 = A[i]
			ch2 = chr(j)
			for i in range(n):
				if A[i] == ch1:
					A[i] = ch2
				elif A[i] == ch2:
					A[i] = ch1
		return ''.join(A)


import heapq

class Solution:

	def chooseandswap(self, s):
		un = list(set(s))
		un = sorted(un)
		uns = set(s)
		for i in range(len(s)):
			if s[i] in uns:
				un.remove(s[i])
				uns.remove(s[i])
			if len(un) == 0:
				break
			if ord(un[0]) < ord(s[i]):
				sec = un[0]
				first = s[i]
				x = 0
				res = ''
				while x < len(s):
					if s[x] == sec:
						res += first
					elif s[x] == first:
						res += sec
					else:
						res += s[x]
					x += 1
				return res
		return s


from collections import defaultdict

class Solution:

	def chooseandswap(self, A):
		if not A:
			return ''
		char_to_indexes = defaultdict(list)
		for (i, char) in enumerate(A):
			char_to_indexes[char].append(i)
		(ch1, ch2) = self.findSwapChar(char_to_indexes, A)
		if not ch1:
			return A
		result = list(A)
		for i in char_to_indexes[ch1]:
			result[i] = ch2
		for j in char_to_indexes[ch2]:
			result[j] = ch1
		return ''.join(result)

	def findSwapChar(self, char_to_indexes, A):
		for (i, swap_char1) in enumerate(A):
			swap_char2 = swap_char1
			for j in range(i + 1, len(A)):
				if A[j] < swap_char1 and char_to_indexes[A[j]][0] > char_to_indexes[swap_char1][0]:
					swap_char2 = min(A[j], swap_char2)
			if swap_char1 != swap_char2:
				return (swap_char1, swap_char2)
		return (None, None)


from collections import defaultdict

class Solution:

	def chooseandswap(self, A):
		if not A:
			return ''
		char_to_indexes = defaultdict(list)
		for (i, item) in enumerate(A):
			char_to_indexes[item].append(i)
		(a, b) = self.findSwapChar(char_to_indexes, A)
		if b == '':
			return A
		result = list(A)
		for i in char_to_indexes[a]:
			result[i] = b
		for j in char_to_indexes[b]:
			result[j] = a
		return ''.join(result)

	def findSwapChar(self, char_to_indexes, A):
		skip_char = set()
		for (i, char) in enumerate(A):
			swap_char = char
			for j in range(i + 1, len(A)):
				if A[j] not in skip_char and A[j] < char and (char_to_indexes[A[j]][0] > char_to_indexes[char][0]):
					swap_char = min(A[j], swap_char)
			if char != swap_char:
				return (char, swap_char)
			skip_char.add(char)
		return ('', '')


class Solution:

	def chooseandswap(self, A):
		A = list(A)
		s = sorted(set(A))
		for i in A:
			if i in s:
				s.remove(i)
			if len(s) == 0:
				break
			e = s[0]
			if e < i:
				for j in range(len(A)):
					if A[j] == e:
						A[j] = i
					elif A[j] == i:
						A[j] = e
				break
		return ''.join(A)


class Solution:

	def chooseandswap(self, A):
		n = len(A)
		occurrences = buildMap(A)
		(new_chr, old_chr) = pickSwaps(occurrences, A)
		if new_chr == None:
			return A
		else:
			ans = ''
			for ch in A:
				if ch == new_chr:
					ans += old_chr
				elif ch == old_chr:
					ans += new_chr
				else:
					ans += ch
			return ans

def buildMap(s):
	first_occurrences = [-1] * 26
	for (i, chr) in enumerate(s):
		if first_occurrences[ord(chr) - ord('a')] == -1:
			first_occurrences[ord(chr) - ord('a')] = i
	return first_occurrences

def pickSwaps(occurrences, s):
	done = False
	for i in range(len(s)):
		idx_in_occurrences = ord(s[i]) - ord('a')
		for j in range(idx_in_occurrences):
			if occurrences[j] > i:
				return (chr(j + ord('a')), s[i])
	return (None, None)


MAX = 256

class Solution:

	def chooseandswap(self, A):
		(i, j) = (0, 0)
		d = {}
		for letter in A:
			d[letter] = True
		for letter in A:
			for char in [chr(l) for l in range(ord('a'), ord(letter))]:
				if char in d and d[char]:
					A = A.replace(letter, '*')
					A = A.replace(char, letter)
					A = A.replace('*', char)
					return A
			d[letter] = False
		return A


MAX_CHAR = 26

class Solution:

	def chooseandswap(self, A):
		chk = [-1] * MAX_CHAR
		for (i, ch) in enumerate(A):
			idx = ord(ch) - ord('a')
			if chk[idx] == -1:
				chk[idx] = i
		n = len(A)
		i = 0
		j = -1
		while i < n:
			flag = False
			ch_idx = ord(A[i]) - ord('a')
			for idx in range(ch_idx):
				if chk[idx] > chk[ch_idx]:
					flag = True
					j = idx
					break
			if flag:
				break
			i += 1
		if i < n - 1:
			res = ''
			ch1 = A[i]
			ch2 = chr(j + ord('a'))
			for i in range(n):
				if A[i] == ch1:
					res += ch2
				elif A[i] == ch2:
					res += ch1
				else:
					res += A[i]
			return res
		return A


class Solution:

	def chooseandswap(self, a):
		fc = ''
		i = 0
		flag = False
		sc = ''
		for i in range(len(a)):
			fc = a[i]
			for j in range(ord('a'), ord(fc)):
				if chr(j) in a[i + 1:] and chr(j) not in a[:i]:
					sc = chr(j)
					flag = True
					break
			if flag:
				break
		if sc == '':
			return a
		for i in range(len(a)):
			if a[i] == fc:
				a = a[:i] + sc + a[i + 1:]
			elif a[i] == sc:
				a = a[:i] + fc + a[i + 1:]
		return a
		pass


class Solution:

	def chooseandswap(self, A):
		a_asc = 97
		firsts = [-1] * 26
		n = len(A)
		for i in range(n):
			asci = ord(A[i]) - a_asc
			if firsts[asci] == -1:
				firsts[asci] = i
		checked = set()
		for i in range(n):
			index = ord(A[i]) - a_asc
			for j in range(index):
				if firsts[j] != -1 and firsts[j] > i:
					swap1 = A[i]
					swap2 = A[firsts[j]]
					res = ''
					for k in range(n):
						if A[k] == swap1:
							res += swap2
						elif A[k] == swap2:
							res += swap1
						else:
							res += A[k]
					return res
		return A


class Solution:

	def chooseandswap(self, s):
		l = [-1] * 26
		n = len(s)
		(x1, x2) = ('', '')
		for i in range(n):
			if l[ord(s[i]) - 97] == -1:
				l[ord(s[i]) - 97] = i
		for i in range(n):
			x = ord(s[i]) - 97
			f = False
			for j in range(x):
				if l[j] > i:
					(x1, x2) = (s[l[j]], s[i])
					f = True
					break
			if f:
				break
		if f:
			s = s.replace(x1, '#')
			s = s.replace(x2, x1)
			s = s.replace('#', x2)
		return s


class Solution:

	def chooseandswap(self, A):
		vis = set()
		ls = []
		k = -1
		for i in A:
			if i not in vis:
				k += 1
				vis.add(i)
				ls.append([i, k])
		ls.sort(key=lambda x: [x[0]])
		ch1 = 0
		ch2 = 0
		for i in range(len(ls)):
			if ls[i][1] != i:
				ch1 = ls[i][0]
				break
		if i == len(ls) - 1:
			return A
		for k in range(i, len(ls)):
			if ls[k][1] == i:
				ch2 = ls[k][0]
				break
		if ch1 != 0 and ch2 != 0:
			k = list(A)
			for i in range(len(k)):
				if k[i] == ch1:
					k[i] = ch2
				elif k[i] == ch2:
					k[i] = ch1
			return ''.join(k)
		return A


class Solution:

	def chooseandswap(self, A):
		l = list(set(A))
		l.sort()
		x = None
		y = None
		for i in A:
			if i in l:
				l.remove(i)
			if l:
				if ord(l[0]) < ord(i):
					x = l[0]
					y = i
					break
		s = ''
		for i in range(len(A)):
			if A[i] == y:
				s += x
			elif A[i] == x:
				s += y
			else:
				s += A[i]
		return s


class Solution:

	def chooseandswap(self, a):
		m = {}
		n = len(a)
		for i in range(n):
			x = a[i]
			if x not in m:
				m[x] = i
		temp = []
		for x in m.keys():
			temp.append([x, m[x]])
		temp.sort()
		(i, j) = (0, 0)
		flag = False
		while i < n:
			j = 0
			while j < len(temp):
				if temp[j][0] < a[i] and temp[j][1] > i:
					j = temp[j][1]
					flag = True
					break
				j += 1
			if flag:
				break
			i += 1
		if i == n:
			return a
		first = a[i]
		sec = a[j]
		ans = ''
		for x in a:
			if x == first:
				ans += sec
			elif x == sec:
				ans += first
			else:
				ans += x
		return ans


class Solution:

	def chooseandswap(self, A):
		d = {}
		a = [0] * 26
		for i in A:
			a[ord(i) - ord('a')] += 1
		a1 = a2 = ''
		for i in range(len(A)):
			r = ''
			for j in range(0, ord(A[i]) - ord('a')):
				if a[j] != 0 and chr(j + ord('a')) not in d:
					r = chr(j + ord('a'))
					break
			if r != '':
				a1 = A[i]
				a2 = r
				break
			d[A[i]] = 1
			a[ord(A[i]) - ord('a')] -= 1
		if a1 != '':
			s1 = ''
			for x in A:
				if x == a1:
					s1 += a2
				elif x == a2:
					s1 += a1
				else:
					s1 += x
			return s1
		return A


class Solution:

	def chooseandswap(self, A):
		arr = [0] * 26
		for k in A:
			arr[ord(k) - ord('a')] = arr[ord(k) - ord('a')] + 1
		ans = {}
		for ch in A:
			f = False
			for l in range(ord(ch) - ord('a')):
				if arr[l] > 0:
					ans[chr(ord('a') + l)] = ch
					ans[ch] = chr(ord('a') + l)
					f = True
					break
			arr[ord(ch) - ord('a')] = 0
			if f:
				break
		st = ''
		for l in A:
			if l in ans:
				st = st + ans[l]
			else:
				st = st + l
		return st


class Solution:

	def chooseandswap(self, s):
		a = [-1] * 26
		n = len(s)
		(x1, x2) = ('', '')
		for i in range(n):
			if a[ord(s[i]) - 97] == -1:
				a[ord(s[i]) - 97] = i
		for i in range(n):
			f = False
			for j in range(ord(s[i]) - 97):
				if a[j] != -1 and a[j] > i:
					x1 = chr(j + 97)
					x2 = s[i]
					f = True
					break
			if f:
				break
		if f:
			s = s.replace(x1, '#')
			s = s.replace(x2, x1)
			s = s.replace('#', x2)
		return s


class Solution:

	def chooseandswap(self, A):
		d = {}
		for l in A:
			d[l] = True
		for l in A:
			for c in [chr(i) for i in range(ord('a'), ord(l))]:
				if c in d and d[c]:
					A = A.replace(l, '*')
					A = A.replace(c, l)
					A = A.replace('*', c)
					return A
			d[l] = False
		return A


class Solution:

	def chooseandswap(self, str):
		n = len(str)
		arr = [-1] * 26
		for i in range(n - 1, -1, -1):
			arr[ord(str[i]) - ord('a')] = i
		for i in range(n):
			for j in range(26):
				if arr[j] > i and ord(str[i]) - ord('a') > j:
					x = str[i]
					y = chr(ord('a') + j)
					str = str.replace(x, '#')
					str = str.replace(y, x)
					str = str.replace('#', y)
					return str
		return str


class Solution:

	def chooseandswap(self, A):
		relpos = {}
		for (i, ch) in enumerate(A):
			relpos[ch] = True
		for ch in A:
			ls = [chr(i) for i in range(ord('a'), ord(ch))]
			for c in ls:
				if c in relpos and relpos[c]:
					A = A.replace(c, '*')
					A = A.replace(ch, c)
					A = A.replace('*', ch)
					return A
			relpos[ch] = False
		return A


class Solution:

	def __init__(self):
		self.aord = ord('a')
		self.alpha_cnt = [-1] * 26

	def c2i(self, c):
		return ord(c) - self.aord

	def i2c(self, i):
		return chr(i + self.aord)

	def smallest_right(self, ci, cpos):
		for j in range(ci):
			if self.alpha_cnt[j] > cpos:
				return j
		return -1

	def show_alpha(self):
		for i in range(26):
			if self.alpha_cnt[i] != -1:
				print('[%c]:%d' % (self.i2c(i), self.alpha_cnt[i]), end=' ')
		print()

	def chooseandswap(self, A):
		first_char = None
		sec_char = None
		ans = None
		self.alpha_cnt = [-1 for __ in range(26)]
		for i in range(len(A)):
			j = self.c2i(A[i])
			if self.alpha_cnt[j] == -1:
				self.alpha_cnt[j] = i
		for i in range(len(A)):
			j = self.c2i(A[i])
			if self.alpha_cnt[j] != -1:
				pos = self.smallest_right(j, self.alpha_cnt[j])
				if pos >= 0:
					first_char = A[i]
					sec_char = self.i2c(pos)
					break
		if first_char is not None:
			nstr = ''
			for c in A:
				if c == first_char:
					nstr += sec_char
				elif c == sec_char:
					nstr += first_char
				else:
					nstr += c
			if nstr < A:
				ans = nstr
			else:
				ans = A
		else:
			ans = A
		return ans

class Solution1:

	def __init__(self):
		self.aord = ord('a')
		self.alpha_cnt = [-1] * 26

	def c2i(self, c):
		return ord(c) - self.aord

	def i2c(self, i):
		return chr(i + self.aord)

	def smallest_right(self, cpos):
		for j in range(26):
			if self.alpha_cnt[j] > cpos:
				return j
		return -1

	def show_alpha(self):
		for i in range(26):
			if self.alpha_cnt[i] != -1:
				print('[%c]:%d' % (self.i2c(i), self.alpha_cnt[i]), end=' ')
		print()

	def chooseandswap(self, A):
		first_char = None
		sec_char = None
		ans = None
		for i in range(len(A)):
			j = self.c2i(A[i])
			if self.alpha_cnt[j] == -1:
				self.alpha_cnt[j] = i
		for i in range(len(A)):
			j = self.c2i(A[i])
			if self.alpha_cnt[j] != -1:
				pos = self.smallest_right(self.alpha_cnt[j])
				if pos >= 0:
					first_char = A[i]
					sec_char = self.i2c(pos)
					break
		if first_char is not None:
			nstr = ''
			for c in A:
				if c == first_char:
					nstr += sec_char
				elif c == sec_char:
					nstr += first_char
				else:
					nstr += c
			if nstr < A:
				ans = nstr
			else:
				ans = A
		else:
			ans = A
		return ans