You are given a string str 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.
 
Exampel 1:
Input: str = "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: "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 and so the answer is abba.
 
Your Task:
You don't need to read or print anything. Your task is to complete the function LexicographicallyMinimum() which takes string str as input parameter and retruns the lexicographically minimum possible string after doing the operation.
 
Expected Time Complexity: O(n)
Expected Space Complexity: O(1)
 
Constraints:
1 <= |str| <= 10^{4}

Difficulty: EASY
Tags: Greedy algorithms
Skill types: Greedy algorithms
Expected Time Complexity: O(n)
Expected Auxiliary Space: O(1)

Starter code:
#User function Template for python3

class Solution:
	def LexicographicallyMinimum(self, str):
		# Code here

Solutions:
class Solution:

	def LexicographicallyMinimum(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 LexicographicallyMinimum(self, str):
		A = str
		s = sorted(set(A))
		swap_a = None
		swap_b = None
		for item in A:
			if ord(item) > ord(s[0]):
				swap_a = item
				swap_b = s[0]
				break
			elif ord(item) == ord(s[0]):
				s.pop(0)
			if len(s) == 0:
				return A
		A = list(A)
		for index in range(len(A)):
			if A[index] == swap_a:
				A[index] = swap_b
			elif A[index] == swap_b:
				A[index] = swap_a
		return ''.join(A)


class Solution:

	def LexicographicallyMinimum(self, str):
		char = [-1] * 256
		for i in range(len(str)):
			if char[ord(str[i])] == -1:
				char[ord(str[i])] = i
		for i in range(len(str)):
			flag = False
			for j in range(ord(str[i])):
				if char[j] > i:
					flag = True
					break
			if flag:
				break
		s1 = str[i]
		s2 = str[char[j]]
		stri = ''
		for i in str:
			if i != s1 and i != s2:
				stri += i
			elif i == s1:
				stri += s2
			else:
				stri += s1
		return stri


class Solution:

	def LexicographicallyMinimum(self, stri):
		items = sorted(set(stri), reverse=True)
		pool = set()
		flag = False
		for item in stri:
			if items and item == items[-1]:
				pool.add(items.pop())
			if item not in pool:
				swap1 = item
				swap2 = items[-1]
				flag = True
				break
		if flag:
			result = ''
			for item in stri:
				if item == swap1:
					result += swap2
				elif item == swap2:
					result += swap1
				else:
					result += item
		return result if flag else stri


class Solution:

	def LexicographicallyMinimum(self, str):
		A = str
		s = sorted(set(A))
		a = None
		b = None
		for i in A:
			if ord(i) > ord(s[0]):
				a = i
				b = s[0]
				break
			elif ord(i) == ord(s[0]):
				s.pop(0)
			if len(s) == 0:
				return A
		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)
if __name__ == '__main__':
	T = int(input())
	for i in range(T):
		str = input()
		ob = Solution()
		ans = ob.LexicographicallyMinimum(str)
		print(ans)


class Solution:

	def LexicographicallyMinimum(self, str):
		s = str
		n = len(s)
		if n <= 1:
			return s
		chars = sorted(set(s))
		(i, j) = (0, 0)
		while i < n and j < len(chars):
			if s[i] == chars[j]:
				i += 1
				j += 1
			elif s[i] > chars[j]:
				ans = s.replace(s[i], '0').replace(chars[j], s[i]).replace('0', chars[j])
				return ans
			else:
				i += 1
		return s


from collections import Counter

class Solution:

	def LexicographicallyMinimum(self, str1):
		m = list(str1)
		j = m.copy()
		k = m.copy()
		k = set(k)
		k = list(k)
		k.sort()
		h = []
		y = 0
		f = 0
		for i in range(len(m)):
			if m[i] in h:
				f = f - 1
			if k[f] != m[i]:
				a = k[f]
				b = m[i]
				y = 1
				break
			else:
				h.append(m[i])
				f = f + 1
		if y == 1:
			for i in range(len(m)):
				if m[i] == a:
					m[i] = b
				elif m[i] == b:
					m[i] = a
				else:
					continue
			if j < m:
				return ''.join(j)
			return ''.join(m)
		else:
			return ''.join(m)


class Solution:

	def LexicographicallyMinimum(self, str):
		tmp = sorted(str)
		c1 = '$'
		c2 = '$'
		fl = False
		for i in range(len(str)):
			k = str.index(tmp[i])
			for j in range(k):
				if str[j] > tmp[i]:
					c1 = str[j]
					c2 = tmp[i]
					fl = True
					break
			if fl:
				break
		res = ''
		for x in str:
			if x == c1:
				res += c2
			elif x == c2:
				res += c1
			else:
				res += x
		return res


from collections import Counter

class Solution:

	def LexicographicallyMinimum(self, str1):
		s = str1.lower()
		l = list(s)
		keys = []
		if len(s) == 1:
			return s
		for i in l:
			if i not in keys:
				keys.append(i)
			else:
				continue
		x = ''
		y = ''
		for i in range(len(keys)):
			f = keys[i + 1:]
			if len(f) > 0:
				m = min(f)
				if ord(keys[i]) > ord(m):
					x = keys[i].lower()
					y = m.lower()
					break
		m = ''
		for i in s:
			if i == x:
				i = y
				m += i
			elif i == y:
				i = x
				m += i
			else:
				m += i
		return m


class Solution:

	def LexicographicallyMinimum(self, str1):
		m = list(str1)
		j = m.copy()
		k = m.copy()
		k = set(k)
		k = list(k)
		k.sort()
		h = []
		y = 0
		f = 0
		for i in range(len(m)):
			if m[i] in h:
				f = f - 1
			if k[f] != m[i] and m[i] not in h:
				a = k[f]
				b = m[i]
				y = 1
				break
			else:
				h.append(m[i])
				f = f + 1
		if y == 1:
			for i in range(len(m)):
				if m[i] == a:
					m[i] = b
				elif m[i] == b:
					m[i] = a
				else:
					continue
			if j < m:
				return ''.join(j)
			return ''.join(m)
		else:
			return ''.join(m)


class Solution:

	def LexicographicallyMinimum(self, str):
		temp = sorted(str)
		ch1 = '$'
		ch2 = '$'
		flag = False
		for i in range(len(str)):
			k = str.index(temp[i])
			for j in range(k):
				if str[j] > temp[i]:
					ch1 = str[j]
					ch2 = temp[i]
					flag = True
					break
			if flag == True:
				break
		res = ''
		for char in str:
			if char == ch1:
				res += ch2
			elif char == ch2:
				res += ch1
			else:
				res += char
		return res


class Solution:

	def LexicographicallyMinimum(self, str):
		lst = [-1] * 256
		arr = list(str)
		n = len(arr)
		ele1 = 0
		ele2 = 0
		for i in range(n):
			if lst[ord(arr[i])] == -1:
				lst[ord(arr[i])] = i
		for i in range(n):
			tf = False
			for j in range(ord(arr[i])):
				if lst[j] > lst[ord(arr[i])]:
					ele1 = arr[i]
					ele2 = arr[lst[j]]
					tf = True
					break
			if tf != False:
				break
		for i in range(n):
			if arr[i] == ele1:
				arr[i] = ele2
			elif arr[i] == ele2:
				arr[i] = ele1
		return ''.join(arr)


class Solution:

	def LexicographicallyMinimum(self, a):
		s = list(set(a))
		s.sort()
		for smallchar in s:
			smallpos = a.index(smallchar)
			found = False
			for ch in a:
				if ch > smallchar:
					found = True
					break
			if not found:
				continue
			biggerpos = a.index(ch)
			if biggerpos < smallpos:
				a = a.replace(ch, '#')
				a = a.replace(smallchar, ch)
				a = a.replace('#', smallchar)
				return a
		return a


class Solution:

	def LexicographicallyMinimum(self, str):
		(p1, p2) = (-1, -1)
		a = [0] * 26
		for i in range(len(str)):
			a[ord(str[i]) - ord('a')] = 1
		for i in range(len(str)):
			ind = ord(str[i]) - ord('a')
			a[ind] = 0
			for j in range(ind):
				if a[j] == 1:
					p1 = str[i]
					p2 = chr(j + ord('a'))
					break
			if p1 != -1:
				break
		if p1 == -1:
			return str
		ans = ''
		for i in range(len(str)):
			if str[i] == p1:
				ans += p2
			elif str[i] == p2:
				ans += p1
			else:
				ans += str[i]
		return ans


class Solution:

	def LexicographicallyMinimum(self, str):
		a = str
		res = a
		l1 = list(a)
		l2 = set(a)
		l2 = list(l2)
		l2.sort()
		x = 0
		for i in range(len(a)):
			if x == len(l2):
				break
			if ord(l1[i]) > ord(l2[x]):
				res = a.replace(l1[i], '0').replace(l2[x], l1[i]).replace('0', l2[x])
				break
			if ord(l1[i]) == ord(l2[x]):
				x += 1
		return res


class Solution:

	def LexicographicallyMinimum(self, st):
		from heapq import heapify, heappush, heappop
		from collections import defaultdict
		elements = sorted(st)
		l = []
		l.append(elements[0])
		for i in range(1, len(elements)):
			if elements[i] == elements[i - 1]:
				continue
			l.append(elements[i])
		heapify(l)
		visited = defaultdict(lambda : 0)
		for i in range(len(st)):
			if visited[st[i]] == 0:
				visited[st[i]] = 1
				cur = heappop(l)
				if cur < st[i]:
					if visited[cur] == 0:
						st = self.replace(st, cur, st[i])
						return st
		return st

	def replace(self, st, cur, el):
		res = ''
		for i in range(len(st)):
			if st[i] == el:
				res += cur
			elif st[i] == cur:
				res += el
			else:
				res += st[i]
		return res


class Solution:

	def LexicographicallyMinimum(self, str):
		new = str
		arr = []
		x = ''.join(sorted(str))
		for i in x:
			if i not in arr:
				arr.append(i)
		for i in range(len(new)):
			if new[i] in arr:
				arr.remove(new[i])
			else:
				continue
			if len(arr) == 0:
				break
			ch = arr[0]
			if ch < new[i]:
				ch2 = new[i]
				y = new.replace(ch2, '_').replace(ch, ch2).replace('_', ch)
				return y
		return new