0670. Maximum Swap

https://leetcode.com/problems/maximum-swap

Description

You are given an integer num. You can swap two digits at most once to get the maximum valued number.

Return the maximum valued number you can get.

Example 1:

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

Example 2:

**Input:** num = 9973
**Output:** 9973
**Explanation:** No swap.

Constraints:

• 0 <= num <= 108

ac

class Solution {
    public int maximumSwap(int num) {
        char[] chars = String.valueOf(num).toCharArray();
        int len = chars.length;
        int[] lastIndexOfDigit = new int[10];
        for (int i = 0; i < len; i++) {
            int digit = chars[i] - '0';
            lastIndexOfDigit[digit] = i;
        }
        
        for (int i = 0; i < len; i++) {
            int currDigit = chars[i] - '0';
            // Try to find a larger digit after this index i.
            for (int d = 9; d > currDigit; d--) {
                if (lastIndexOfDigit[d] > i) {
                    chars[i] = chars[lastIndexOfDigit[d]];
                    chars[lastIndexOfDigit[d]] = (char)('0' + currDigit);
                    return Integer.parseInt(String.valueOf(chars));
                }
            }
        }
        
        return num;
    }
}

// O(N * 9) time - N is len(num), O(N) space