Given a non-negative number N in the form of a string.Find the largest number that can be formed by swapping two characters at most once.
 
Example 1:
Input:
N=768
Output:
867
Explanation:
Swapping the 1st and 3rd 
characters(7 and 8 respectively),
gives the largest possible number.
Example 2:
Input:
N=333
Output:
333
Explanation:
Performing any swaps gives the 
same result i.e 333.
 
Your Task:
You don't need to read input or print anything. Your task is to complete the function LargestSwap() which takes the string N as input parameter and returns the maximum possible string possible with at most one swap.
Expected Time Complexity:O(|N|)
Expected Auxillary Space:O(1)
Constraints:
1<=|N|<=10^{5}

Difficulty: EASY
Tags: String algorithms

Data structures
Skill types: Data structures
Expected Time Complexity: O(|N|)
Expected Auxiliary Space: O(1)

Starter code:
#User function Template for python3

class Solution:
    def LargestSwap(self,S):
        #code here

Solutions:
class Solution:

	def LargestSwap(self, S):
		n = len(S)
		arr = list(S)
		right = [0] * n
		right[n - 1] = n - 1
		rmax = n - 1
		for i in range(n - 2, -1, -1):
			right[i] = rmax
			if arr[i] > arr[rmax]:
				rmax = i
		for i in range(0, n):
			if arr[right[i]] > arr[i]:
				(arr[right[i]], arr[i]) = (arr[i], arr[right[i]])
				break
		return ''.join(arr)


class Solution:

	def LargestSwap(self, S):
		i = -1
		j = len(S) - 1
		mx = S[-1]
		for x in range(len(S) - 2, -1, -1):
			if S[x] < mx:
				i = x
			elif S[x] > mx:
				mx = S[x]
				j = x
		if i == -1:
			return S
		S = list(S)
		(S[i], S[j]) = (S[j], S[i])
		S = ''.join(S)
		return S


class Solution:

	def LargestSwap(self, S):
		n = len(S)
		arr = list(S)
		hm = {i: -1 for i in range(0, 10)}
		for i in range(0, len(S)):
			hm[int(S[i])] = i
		for i in range(0, n):
			if S[i] != '9':
				d = 9
				curr = int(arr[i])
				f = False
				while curr < d:
					if hm[d] > i:
						(arr[i], arr[hm[d]]) = (arr[hm[d]], arr[i])
						f = True
						break
					d -= 1
				if f == True:
					break
		return ''.join(arr)


class Solution:

	def LargestSwap(self, S):
		arr = list(map(int, S))
		max_val = -1
		for i in range(len(arr) - 1, -1, -1):
			if arr[i] > max_val:
				max_val = arr[i]
				index = i
		for i in range(len(arr)):
			if arr[i] < max_val:
				i = i
				break
		if index < i:
			return S
		(arr[i], arr[index]) = (arr[index], arr[i])
		return ''.join(map(str, arr))


class Solution:

	def LargestSwap(self, S):
		l = len(S)
		max1 = 0
		max2 = 1
		max3 = 1
		flag = 0
		for i in range(1, l):
			if S[i] >= S[max1] and S[i] != '0':
				max1 = i
			if S[i] > S[i - 1] and flag == 0:
				max3 = i
				flag = 1
		ans = S
		if max1 != 0 and S[max1] > S[0]:
			ans = ''.join((S[:0], S[max1], S[1:max1], S[0], S[max1 + 1:]))
		else:
			max2 = l - 1
			for i in range(l - 2, max3, -1):
				if S[i] > S[max2]:
					max2 = i
			for i in range(1, max2):
				if S[i] < S[max2]:
					ans = ''.join((S[:i], S[max1], S[i + 1:max1], S[i], S[max1 + 1:]))
					break
		return ans


class Solution:

	def LargestSwap(self, S):
		max_ele = -1
		max_index = None
		l_index = None
		r_index = None
		for i in range(len(S) - 1, -1, -1):
			if int(S[i]) > max_ele:
				max_ele = int(S[i])
				max_index = i
				continue
			elif int(S[i]) < max_ele:
				l_index = i
				r_index = max_index
		if l_index == None:
			return S
		S = list(S)
		(S[l_index], S[r_index]) = (S[r_index], S[l_index])
		return ''.join(S)