Given an odd number in the form of string, the task is to make largest even number possible from the given number provided one is allowed to do only one swap operation, if no such number is possible then return the input string itself.
Example 1:
Input:
s = 4543
Output: 4534
Explanation: Swap 4(3rd pos) and 3.
 
Example 2:
Input:
s = 1539
Output: 1539
Explanation: No even no. present.
 
Your Task:  
You dont need to read input or print anything. Complete the function makeEven() which takes a string s as input parameter and returns a string after performing given operations.
 
Expected Time Complexity: O(Length of Input string).
Expected Auxiliary Space: O(1).
 
Constraints:
1 <= Length of odd number string<= 10^{5}

Difficulty: EASY
Tags: String algorithms

Data structures
Skill types: Data structures
Expected Time Complexity: O(Length of Input string).
Expected Auxiliary Space: O(1).

Starter code:
#User function Template for python3



class Solution:

    def makeEven(self, s):

        # code here

Solutions:
class Solution:

	def makeEven(self, s):
		s = list(s)
		for i in range(len(s)):
			if int(s[i]) < int(s[-1]) and int(s[i]) % 2 == 0:
				(s[i], s[-1]) = (s[-1], s[i])
				return ''.join(s)
		for i in range(1, len(s) + 1):
			if int(s[-i]) > int(s[-1]) and int(s[-i]) % 2 == 0:
				(s[-i], s[-1]) = (s[-1], s[-i])
				return ''.join(s)
		return ''.join(s)


class Solution:

	def makeEven(self, s):
		n = len(s)
		k = n - 1
		for i in range(k):
			if int(s[i]) % 2 == 0:
				k = i
				if int(s[i]) < int(s[-1]):
					break
		s = list(s)
		(s[k], s[-1]) = (s[-1], s[k])
		return ''.join(s)


class Solution:

	def makeEven(self, s):
		lastNumber = int(s[-1])
		num = -1
		ind = -1
		even = 0
		for i in range(len(s)):
			if int(s[i]) % 2 == 0:
				even = 1
				if int(s[i]) < lastNumber:
					num = int(s[i])
					ind = i
					break
		if num == -1:
			j = len(s) - 2
			while j >= 0:
				if int(s[j]) % 2 == 0:
					num = int(s[j])
					ind = j
					break
				else:
					j -= 1
			if j < 0:
				return s
			elif j == len(s) - 2:
				s = s[:ind] + s[-1] + s[-2]
			else:
				s = s[:ind] + s[-1] + s[j + 1:-1] + str(num)
		else:
			s = s[:i] + str(lastNumber) + s[i + 1:-1] + str(num)
		return s


class Solution:

	def makeEven(self, s):
		n = len(s)
		mei = -1
		for (i, e) in enumerate(Str):
			if int(e) % 2 == 0 and int(e) < int(s[-1]):
				mei = i
				break
			elif int(e) % 2 == 0:
				mei = i
		if mei == -1:
			return s
		ans = s[:mei] + s[-1] + s[mei + 1:n - 1] + s[mei]
		return ans


class Solution:

	def makeEven(self, s):
		lst = list(s)
		f = -1
		l = -1
		li = len(s) - 1
		for i in range(len(s)):
			if int(s[i]) % 2 == 0 and int(s[i]) < int(s[li]):
				f = i
				break
			if int(s[i]) % 2 == 0:
				l = i
		if f != -1:
			(lst[f], lst[li]) = (lst[li], lst[f])
			return ''.join(lst)
		if f == -1 and l != -1:
			(lst[f], lst[l]) = (lst[l], lst[f])
			return ''.join(lst)
		return s


class Solution:

	def makeEven(self, s):
		list_1 = list(s.strip(' '))
		last = -1
		for i in range(len(list_1)):
			current_digit = list_1[i]
			last_digit = list_1[-1]
			if int(current_digit) % 2 == 0:
				if int(current_digit) < int(last_digit):
					list_1[-1] = current_digit
					list_1[i] = last_digit
					return ''.join(list_1)
				else:
					last = i
		last_digit = list_1[-1]
		list_1[-1] = list_1[last]
		list_1[last] = last_digit
		return ''.join(list_1)


class Solution:

	def makeEven(self, s):
		if len(s) == 1:
			return s
		l = None
		for i in range(len(s) - 1):
			if int(s[i]) % 2 == 0:
				l = i
				if s[i] < s[-1]:
					break
		if l == None:
			return s
		s = list(s)
		(s[l], s[-1]) = (s[-1], s[l])
		return ''.join(s)


class Solution:

	def makeEven(self, s):
		num = list(s)
		even_idx = [i for i in range(len(num)) if int(num[i]) % 2 == 0]
		for i in even_idx:
			if num[i] < num[-1]:
				(num[i], num[-1]) = (num[-1], num[i])
				return ''.join(num)
			elif even_idx.index(i) == len(even_idx) - 1:
				(num[i], num[-1]) = (num[-1], num[i])
				return ''.join(num)
		return s


class Solution:

	def makeEven(self, s):
		arr = []
		for i in s:
			arr.append(int(i))
		even = -float('inf')
		largest_even = -1
		swap = False
		for i in range(len(arr)):
			if arr[i] % 2 == 0:
				if arr[i] < arr[-1]:
					(arr[i], arr[-1]) = (arr[-1], arr[i])
					swap = True
					break
				largest_even = i
		if swap == False and largest_even != -1:
			(arr[-1], arr[largest_even]) = (arr[largest_even], arr[-1])
		ans = ''
		for i in arr:
			ans += str(i)
		return ans


class Solution:

	def makeEven(self, s):
		s1 = []
		for i in s:
			s1.append(int(i))
		flag = False
		for i in range(len(s1)):
			if s1[i] % 2 == 0 and s1[i] < s1[-1]:
				temp = s1[-1]
				s1[-1] = s1[i]
				s1[i] = temp
				flag = True
				break
		if not flag:
			for i in range(len(s1) - 1, -1, -1):
				if s1[i] % 2 == 0:
					temp = s1[-1]
					s1[-1] = s1[i]
					s1[i] = temp
					break
		s = ''
		for i in s1:
			s += str(i)
		return s


class Solution:

	def makeEven(self, s):
		s = list(s)
		li = len(s) - 1
		fe = -1
		le = -1
		for i in range(len(s)):
			if int(s[i]) % 2 == 0 and int(s[i]) < int(s[li]):
				fe = i
				break
			if int(s[i]) % 2 == 0:
				le = i
		if fe != -1:
			(s[fe], s[li]) = (s[li], s[fe])
			return ''.join(s)
		if fe == -1 and le != -1:
			(s[le], s[li]) = (s[li], s[le])
			return ''.join(s)
		return ''.join(s)


class Solution:

	def makeEven(self, s):
		s = list(s)
		idx_swap = -1
		odd_nb = int(s[-1])
		for i in range(len(s)):
			current_nb = int(s[i])
			if current_nb % 2 == 0:
				if odd_nb > current_nb:
					s[i] = str(odd_nb)
					s[-1] = str(current_nb)
					return ''.join(s)
				else:
					idx_swap = i
		temp = s[idx_swap]
		s[idx_swap] = str(odd_nb)
		s[-1] = str(temp)
		return ''.join(s)


class Solution:

	def makeEven(self, n):
		odd = int(n[-1])
		placetoex = -1
		for i in range(len(n) - 1):
			e = int(n[i])
			if e % 2 == 0:
				if e < odd:
					placetoex = i
					break
		if placetoex == -1:
			for i in range(len(n) - 2, -1, -1):
				if int(n[i]) % 2 == 0:
					placetoex = i
					break
		if placetoex == -1:
			return n
		else:
			return n[:placetoex] + n[-1] + n[placetoex + 1:len(n) - 1] + n[placetoex]


class Solution:

	def makeEven(self, s):
		l = []
		m = {'0': 0, '1': 1, '2': 2, '3': 3, '4': 4, '5': 5, '6': 6, '7': 7, '8': 8, '9': 9}
		f = 0
		for i in s:
			l.append(i)
			if m[i] % 2 == 0:
				f = 1
		if f == 0:
			return s
		n = len(l)
		g = -1
		f = 0
		for i in range(n - 1):
			if m[l[i]] % 2 == 0:
				g = i
				if m[l[i]] < m[l[n - 1]]:
					(l[i], l[n - 1]) = (l[n - 1], l[i])
					f = 1
					break
		if f == 0:
			(l[g], l[n - 1]) = (l[n - 1], l[g])
		return ''.join(l)
if __name__ == '__main__':
	T = int(input())
	for tcs in range(T):
		Str = input()
		ob = Solution()
		print(ob.makeEven(Str))


class Solution:

	def makeEven(self, s):
		(eveIndLeft, eveIndRight) = (-1, -1)
		for x in range(len(s)):
			if int(s[x]) % 2 == 0 and int(s[x]) < int(s[-1]):
				eveIndLeft = x
				break
			if int(s[x]) % 2 == 0:
				eveIndRight = x
		arr = list(s)
		if eveIndLeft != -1:
			(arr[eveIndLeft], arr[-1]) = (arr[-1], arr[eveIndLeft])
			return ''.join(arr)
		elif eveIndLeft == -1 and eveIndRight != -1:
			(arr[eveIndRight], arr[-1]) = (arr[-1], arr[eveIndRight])
			return ''.join(arr)
		return s
if __name__ == '__main__':
	T = int(input())
	for tcs in range(T):
		Str = input()
		ob = Solution()
		print(ob.makeEven(Str))


class Solution:

	def makeEven(self, s):
		s = list(s)
		first_e_i = -1
		last_e_i = -1
		last_n_i = len(s) - 1
		for i in range(len(s)):
			if int(s[i]) % 2 == 0 and int(s[i]) < int(s[last_n_i]):
				first_e_i = i
				break
			if int(s[i]) % 2 == 0:
				last_e_i = i
		if first_e_i != -1:
			(s[first_e_i], s[last_n_i]) = (s[last_n_i], s[first_e_i])
			return ''.join(s)
		if first_e_i == -1 and last_e_i != -1:
			(s[last_e_i], s[last_n_i]) = (s[last_n_i], s[last_e_i])
			return ''.join(s)
		return ''.join(s)
if __name__ == '__main__':
	T = int(input())
	for tcs in range(T):
		Str = input()
		ob = Solution()
		print(ob.makeEven(Str))


class Solution:

	def makeEven(self, s):
		n = len(s)
		lst = list(map(str, s))
		last_digit = lst[n - 1]
		even = ''
		index = 0
		flag = 0
		for i in range(n - 1):
			current = int(lst[i])
			if current % 2 == 0:
				if current < int(last_digit):
					(lst[i], lst[n - 1]) = (lst[n - 1], lst[i])
					return ''.join(lst)
				else:
					even = str(current)
					index = i
					flag = 1
		if flag:
			(lst[index], lst[n - 1]) = (lst[n - 1], even)
			return ''.join(lst)
		return s
if __name__ == '__main__':
	T = int(input())
	for tcs in range(T):
		Str = input()
		ob = Solution()
		print(ob.makeEven(Str))


class Solution:

	def makeEven(self, s):
		l = [int(i) for i in s]
		max1 = -1
		ind = 0
		max2 = -1
		c = 0
		f = 0
		for i in range(len(l) - 1):
			if l[i] % 2 == 0:
				if l[i] < l[len(l) - 1]:
					(l[i], l[len(l) - 1]) = (l[len(l) - 1], l[i])
					f = 1
					break
		if f == 1:
			s = ''
			for i in l:
				s += str(i)
			return s
		v = len(l) - 1
		i = len(l) - 2
		while i >= 0:
			if l[i] % 2 == 0:
				(l[v], l[i]) = (l[i], l[v])
				break
			i -= 1
		s = ''
		for i in l:
			s += str(i)
		return s
if __name__ == '__main__':
	T = int(input())
	for tcs in range(T):
		Str = input()
		ob = Solution()
		print(ob.makeEven(Str))


class Solution:

	def makeEven(self, s):
		n = len(s)
		k = -1
		for i in range(n):
			if int(s[i]) % 2 == 0:
				k = i
				if int(s[i]) < int(s[-1]):
					break
		if k >= 0:
			return s[:k] + s[-1] + s[k + 1:n - 1] + s[k]
		else:
			return s
if __name__ == '__main__':
	T = int(input())
	for tcs in range(T):
		Str = input()
		ob = Solution()
		print(ob.makeEven(Str))


class Solution:

	def makeEven(self, s):
		n = len(s)
		lastnumi = n - 1
		firsteveni = -1
		lasteveni = -1
		s = list(s)
		if n == 1 or int(s[n - 1]) % 2 == 0:
			return ''.join(s)
		for i in range(n):
			x = int(s[i])
			if x % 2 == 0 and x < int(s[n - 1]):
				firsteveni = i
				break
			if x % 2 == 0:
				lasteveni = i
		if firsteveni != -1:
			(s[firsteveni], s[lastnumi]) = (s[lastnumi], s[firsteveni])
			return ''.join(s)
		elif firsteveni == -1 and lasteveni != -1:
			(s[lasteveni], s[n - 1]) = (s[n - 1], s[lasteveni])
			return ''.join(s)
		return ''.join(s)
if __name__ == '__main__':
	T = int(input())
	for tcs in range(T):
		Str = input()
		ob = Solution()
		print(ob.makeEven(Str))


class Solution:

	def makeEven(self, s):
		arr = []
		n = len(s)
		flag = 0
		for i in s:
			arr.append(i)
		for i in range(n - 1):
			if int(arr[i]) % 2 == 0:
				if int(arr[i]) < int(arr[n - 1]):
					(arr[i], arr[n - 1]) = (arr[n - 1], arr[i])
					flag = 1
					break
		if flag == 0:
			for i in range(n - 1, -1, -1):
				if int(arr[i]) % 2 == 0:
					(arr[i], arr[n - 1]) = (arr[n - 1], arr[i])
					flag = 1
					break
		s = ''
		for i in arr:
			s = s + i
		return s


class Solution:

	def makeEven(self, s):
		n = len(s)
		last = n - 1
		for i in range(0, n):
			if int(s[i]) % 2 == 0 and int(s[i]) < int(s[n - 1]):
				l = list(s)
				(l[i], l[n - 1]) = (l[n - 1], l[i])
				ans = ''.join(l)
				return ans
			elif int(s[i]) % 2 == 0:
				last = i
		l = list(s)
		(l[last], l[n - 1]) = (l[n - 1], l[last])
		ans = ''.join(l)
		return ans


class Solution:

	def makeEven(self, s):
		(k, j, last) = (1, len(s) - 1, len(s) - 1)
		r = [i for i in s]
		for i in range(len(r)):
			if int(r[i]) % 2 == 0 and int(r[i]) < int(r[j]):
				(r[i], r[j]) = (r[j], r[i])
				return ''.join(r)
			elif int(r[i]) % 2 == 0:
				last = i
		(r[last], r[j]) = (r[j], r[last])
		return ''.join(r)


maxValue = 11

class Solution:

	def makeEven(self, S):
		s = list(S)
		even = maxValue
		index = -1
		for i in range(len(s)):
			left = int(s[i])
			right = int(s[-1])
			if left % 2 == 0:
				if left < right:
					even = left
					index = i
					break
				else:
					even = left
					index = i
		if index >= 0:
			temp = s[index]
			s[index] = s[-1]
			s[-1] = temp
			return ''.join(s)
		return S


class Solution:

	def makeEven(self, s):
		s = list(s)
		lastidx = -1
		digit = s[-1]
		for i in range(len(s)):
			if int(s[i]) % 2 == 0:
				if int(digit) > int(s[i]):
					s[-1] = s[i]
					s[i] = digit
					return ''.join(s)
				else:
					lastidx = i
		if lastidx == -1:
			return ''.join(s)
		s[-1] = s[lastidx]
		s[lastidx] = digit
		return ''.join(s)


class Solution:

	def makeEven(self, s):
		l = len(s)
		odd_no = int(s[l - 1])
		end = -1
		res = ''
		for i in range(0, l):
			if int(s[i]) < odd_no and int(s[i]) % 2 == 0:
				end = i
				break
			if int(s[i]) % 2 == 0:
				end = i
		if i == -1:
			return s
		for i in range(0, l - 1):
			if i == end:
				res = res + s[l - 1]
			else:
				res = res + s[i]
		res = res + s[end]
		return res


class Solution:

	def makeEven(self, s):
		l = list(s)
		x = -1
		for i in range(len(l) - 1):
			if int(l[i]) % 2 == 0:
				if int(l[i]) < int(l[-1]):
					x = i
					break
				else:
					x = i
		if x != -1:
			(l[x], l[-1]) = (l[-1], l[x])
			k = int(''.join(l))
			return str(k)
		else:
			return s


class Solution:

	def makeEven(self, s):
		k = list(s)
		fi = -1
		li = -1
		for i in range(len(k) - 1):
			if int(k[i]) % 2 == 0 and int(k[i]) < int(k[-1]):
				fi = i
				break
			if int(k[i]) % 2 == 0:
				li = i
		if fi != -1:
			(k[fi], k[-1]) = (k[-1], k[fi])
			return ''.join(k)
		if fi == -1:
			(k[li], k[-1]) = (k[-1], k[li])
			return ''.join(k)
		return ''.join(k)


import math

class Solution:

	def makeEven(self, s):
		s = list(s)
		f = 0
		for i in range(len(s)):
			if int(s[i]) % 2 == 0 and int(s[i]) < int(s[-1]):
				f = 1
				index_i = i
				break
			if int(s[i]) % 2 == 0:
				f = 1
				index_i = i
		if f == 1:
			(s[index_i], s[-1]) = (s[-1], s[index_i])
		return ''.join(s)


class Solution:

	def makeEven(self, s):
		a = list(s)
		l = len(a)
		index = 0
		flag = 0
		for i in range(l):
			if int(a[i]) % 2 == 0:
				flag = 1
				index = i
			if int(a[i]) % 2 == 0 and int(a[i]) < int(a[-1]):
				flag = 1
				index = i
				break
		if flag == 1:
			(a[index], a[-1]) = (a[-1], a[index])
		return ''.join(a)


class Solution:

	def makeEven(self, s):
		j = len(s) - 1
		s = list(s)
		i = 0
		while i < len(s):
			if int(s[i]) % 2 == 0 and s[i] < s[-1]:
				(s[i], s[-1]) = (s[-1], s[i])
				return ''.join(s)
			i += 1
		j = len(s) - 1
		while j >= 0:
			if int(s[j]) % 2 == 0:
				(s[j], s[-1]) = (s[-1], s[j])
				return ''.join(s)
			j -= 1
		return ''.join(s)


class Solution:

	def makeEven(self, s):
		s = list(s)
		first_e_i = -1
		last_e_i = -1
		last_n_i = len(s) - 1
		for x in range(len(s)):
			if int(s[x]) % 2 == 0 and int(s[x]) < int(s[last_n_i]):
				first_e_i = x
				break
			if int(s[x]) % 2 == 0:
				last_e_i = x
		if first_e_i != -1:
			(s[first_e_i], s[last_n_i]) = (s[last_n_i], s[first_e_i])
			return ''.join(s)
		if first_e_i == -1 and last_e_i != -1:
			(s[last_n_i], s[last_e_i]) = (s[last_e_i], s[last_n_i])
			return ''.join(s)
		return ''.join(s)