Home
Algorithms Data Structures Interview Experiences
Amazon Google Facebook Microsoft Apple Netflix
Play 2048 How to

LeetCode Solutions

670. Maximum Swap

Time: $O(n)$

Space: $O(n)$

			


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;
  }
};




			


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;
  }
}




			


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