Given a non-negative integer, you could swap two digits at most once to get the maximum valued number. Return the maximum valued number you could get.


Example 1:

Input: 2736
Output: 7236
Explanation: Swap the number 2 and the number 7.



Example 2:

Input: 9973
Output: 9973
Explanation: No swap.




Note:

The given number is in the range [0, 108]

Difficulty: interview

Starter code:

class Solution:
    def maximumSwap(self, num: int) -> int:
        

Solutions:
class Solution:
     def maximumSwap(self, num):
         """
         :type num: int
         :rtype: int
         """
         s = str(num)
         nums = [int(_) for _ in s]
         dp = [-1]*len(nums)
         for i in range(len(nums)-1,-1,-1):
             if i==len(nums)-1:
                 dp[i] = i
             else:
                 dp[i] = i if nums[i]>nums[dp[i+1]] else dp[i+1]
         
         for i in range(len(nums)):
             if nums[i] != nums[dp[i]]:
                 nums[i],nums[dp[i]] = nums[dp[i]],nums[i]
                 break
         res = 0
         for num in nums:
             res = res*10 + num
         return res
                 
             
         
         
         
         
         
         
         
         
         
         
         
         
         
         
         
         
         
         
         


class Solution:
     def maximumSwap(self, num):
         """
         :type num: int
         :rtype: int
         """
         digits = ""
         while(int(num)):
             digits += str(int(num%10))
             num/=10
             
         #print(digits)
         digits = digits[::-1]
         lens = len(digits)
         mark = 0
         mark1 = 0
         flag = 0
         for i in range(lens):
             maxs = ord(digits[i])
             for j in range(i+1, lens,1):
                 if ord(digits[j]) >= maxs:
                     maxs = ord(digits[j])
                     mark = j
             if maxs != ord(digits[i]):
                 mark1 = i
                 flag = 1
                 break;
         #print(digits)
         digit = list(digits)
         #print(digit)
         if flag == 1:
             tem = digit[mark1]
             digit[mark1] = digit[mark]
             digit[mark] = tem
         #print(digit)
         #digits = digits[::-1]
         res = 0
         #print(digit)
         for i in range(lens):
             res *= 10
             res += ord(digit[i]) - ord('0')
             #print(res)
         return res

class Solution:
     def maximumSwap(self, num):
         """
         :type num: int
         :rtype: int
         """
         s = str(num)
         self.res = s
 
         def swap(i, j):
             a, b = self.res[i], self.res[j]
             self.res = self.res[:i] + b + self.res[i + 1:]
             self.res = self.res[:j] + a + self.res[j + 1:]
 
         d = {}
 
         for i, c in enumerate(s):
             if c in d:
                 d[c].append(i)
             else:
                 d[c] = [i]
 
         c = 0
         for i in range(10)[::-1]:
             i = str(i)
             if i in d:
                 arr = d[i]
                 done = False
 
                 for e in arr:
                     if e != c:
                         swap(c, arr[-1])
                         done = True
                         break
                     c += 1
 
                 if done:
                     break
 
         return int(self.res)

class Solution:
     def maximumSwap(self, num):
         """
         :type num: int
         :rtype: int
         """
         import itertools
         
         # Convert num into a list of chars
         A = [c for c in str(num)]
         
         # Compute suffix max for A
         suff_max = list(itertools.accumulate(A[::-1], max))[::-1]
         
         # Compute char -> largest index in A
         last = {x : i for i, x in enumerate(A)}
         
         # Find the first mismatch in A and suff_max
         try:
             i, x, y = next((i, x, y) for i, (x, y) in enumerate(zip(A, suff_max)) if x != y)
         except StopIteration:
             return num
         
         # Swap the A[i] with the farthest appearance of y in A
         A[i], A[last[y]] = A[last[y]], A[i]
         
         return int(''.join(A))

class Solution:
     def maximumSwap(self, num):
         """
         :type num: int
         :rtype: int
         """
         import itertools
         
         # Convert num into a list of chars
         A = [c for c in str(num)]
         
         # Compute suffix max for A
         suff_max = list(itertools.accumulate(A[::-1], max))[::-1]
         
         # Compute char -> largest index in A
         last = {x : i for i, x in enumerate(A)}
 
         # Swap the first occurrence of A[i] < suff_max[i]
         for i, x in enumerate(A):
             if x < suff_max[i]:
                 A[i], A[last[suff_max[i]]] = A[last[suff_max[i]]], A[i]
                 break
 
         return int(''.join(A))

class Solution:
     def maximumSwap(self, num):
         """
         :type num: int
         :rtype: int
         """
         A = list(str(num))
         ans = A[:]
         for i in range(len(A)):
             for j in range(i+1, len(A)):
                 A[i], A[j] = A[j], A[i]
                 if A > ans: ans = A[:]
                 A[i], A[j] = A[j], A[i]
 
         return int("".join(ans))


class Solution:
     def maximumSwap(self, num):
         arr = str(num)
         n = len(arr)
         posmax = [0] * n
         posmax[-1] = n-1
         pow10 = [0] * n
         pow10[-1] = 1        
         for i in range(n-2, -1, -1):
             if arr[i] > arr[posmax[i+1]]:
                 posmax[i] = i
             else:
                 posmax[i] = posmax[i+1]
             pow10[i] = pow10[i+1] * 10
         for i in range(n):
             if arr[i] == '9':
                 continue
             j = posmax[i]
             if arr[j] > arr[i]:
                 x = int(arr[i])
                 y = int(arr[j])
                 return num + pow10[i]*(-x + y) + pow10[j]*(-y + x)
         return num
     


class Solution:
     def maximumSwap(self, num):
         arr = [int(c) for c in str(num)]
         n = len(arr)
         posmax = [0] * n
         posmax[-1] = n-1
         for i in range(n-2, -1, -1):
             if arr[i] > arr[posmax[i+1]]:
                 posmax[i] = i
             else:
                 posmax[i] = posmax[i+1]
         for i in range(n):
             if arr[i] == 9:
                 continue
             j = posmax[i]
             if arr[j] > arr[i]:
                 arr[i], arr[j] = arr[j], arr[i]
                 return int(''.join(map(str, arr)))
         return num
     


class Solution:
     def maximumSwap(self, num):
         """
         :type num: int
         :rtype: int
         """
         array = list(map(lambda x: int(x), str(num)))
         stack = []
         l = float('inf')
         r = None
         for i, d in enumerate(array):
             while stack and array[stack[-1]] < d:
                 l = min(l, stack.pop())
             stack.append(i)
             if l < float('inf'):
                 if not r or array[r] <= d:
                     r = i
         if l == float('inf'):
             return num
         else:
             basel = 10 ** (len(array) - 1 - l)
             baser = 10 ** (len(array) - 1 - r)
             return num + basel*(array[r]-array[l]) + baser*(array[l]-array[r])

class Solution:
     def swap(self, i, c):
         for ii in range(len(self.res))[::-1]:
             if self.res[ii] == c:
                 a, b = self.res[i], self.res[ii]
                 self.res = self.res[:i] + b + self.res[i + 1:]
                 self.res = self.res[:ii] + a + self.res[ii + 1:]
                 break
                     
     def maximumSwap(self, num):
         """
         :type num: int
         :rtype: int
         """
         s = str(num)
         l = sorted(list(s), reverse=True)
         self.res = s
 
         for i, char in enumerate(s):
             if char != l[i]:
                 self.swap(i, l[i])
                 break
 
         return int(self.res)