Maximum Swap

medium greedy string

Problem

Swap two digits at most once to make the number as large as possible.

Inputnum = 2736

Output7236

Swap 2 and 7.

input

def maximum_swap(num):
    s = list(str(num))
    last = {int(d): i for i, d in enumerate(s)}
    for i, d in enumerate(s):
        for D in range(9, int(d), -1):
            if last.get(D, -1) > i:
                j = last[D]; s[i], s[j] = s[j], s[i]; return int(''.join(s))
    return num

function maximumSwap(num) {
  const s = String(num).split('');
  const last = {};
  for (let i = 0; i < s.length; i++) last[s[i]] = i;
  for (let i = 0; i < s.length; i++)
    for (let d = 9; d > +s[i]; d--)
      if ((last[d] ?? -1) > i) { const j = last[d]; [s[i], s[j]] = [s[j], s[i]]; return Number(s.join('')); }
  return num;
}

int maximumSwap(int num) {
    char[] s = String.valueOf(num).toCharArray();
    int[] last = new int[10]; Arrays.fill(last, -1);
    for (int i = 0; i < s.length; i++) last[s[i] - '0'] = i;
    for (int i = 0; i < s.length; i++)
        for (int d = 9; d > s[i] - '0'; d--)
            if (last[d] > i) { char t = s[i]; s[i] = s[last[d]]; s[last[d]] = t; return Integer.parseInt(new String(s)); }
    return num;
}

int maximumSwap(int num) {
    string s = to_string(num);
    vector last(10, -1);
    for (int i = 0; i < (int)s.size(); i++) last[s[i] - '0'] = i;
    for (int i = 0; i < (int)s.size(); i++)
        for (int d = 9; d > s[i] - '0'; d--)
            if (last[d] > i) { swap(s[i], s[last[d]]); return stoi(s); }
    return num;
}

Explanation

To make a number as big as possible with one swap, you want to move a large digit to an early position, because the leftmost digits carry the most value. So we scan from the left and, for each digit, ask: is there a bigger digit somewhere to its right we can pull in?

To answer that quickly, we first record the last (rightmost) index of every digit value 0 through 9 in the table last. The rightmost copy matters because swapping a far-right big digit leftward gains the most.

Then for each position i, we try digit values from 9 down to just above s[i]. The first value that actually appears later in the string (its last index is greater than i) is the best possible upgrade. We swap once and return immediately.

Going high-to-low and left-to-right guarantees the very first successful swap is the most valuable one, so we are done after a single change.

Example: num = 2736. At i=0 the digit is 2; the biggest larger digit later is 7 at index 1. Swap them to get 7236, which is the answer.

Time: O(n) Space: O(n)