Skip to content

670. Maximum Swap 👍

  • Time: $O(n)$
  • Space: $O(n)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
class Solution {
 public:
  int maximumSwap(int num) {
    string s = to_string(num);
    vector<int> lastIndex(10, -1);  // {digit: last index}

    for (int i = 0; i < s.length(); ++i)
      lastIndex[s[i] - '0'] = i;

    for (int i = 0; i < s.length(); ++i)
      for (int d = 9; d > s[i] - '0'; --d)
        if (lastIndex[d] > i) {
          swap(s[i], s[lastIndex[d]]);
          return stoi(s);
        }

    return num;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
class Solution {
  public int maximumSwap(int num) {
    char[] s = Integer.toString(num).toCharArray();
    int[] lastIndex = new int[10]; // {digit: last index}

    for (int i = 0; i < s.length; ++i)
      lastIndex[s[i] - '0'] = i;

    for (int i = 0; i < s.length; ++i)
      for (int d = 9; d > s[i] - '0'; --d)
        if (lastIndex[d] > i) {
          s[lastIndex[d]] = s[i];
          s[i] = (char) ('0' + d);
          return Integer.parseInt(new String(s));
        }

    return num;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
class Solution:
  def maximumSwap(self, num: int) -> int:
    s = list(str(num))
    dict = {c: i for i, c in enumerate(s)}

    for i, c in enumerate(s):
      for digit in reversed(string.digits):
        if digit <= c:
          break
        if digit in dict and dict[digit] > i:
          s[i], s[dict[digit]] = digit, s[i]
          return int(''.join(s))

    return num