# Maximum Swap

## Description

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:**

1. The given number is in the range \[0, $$10^8$$ ]

## Solutions

### My solution

Algorithm:

1. Let `num[i]` denote the $$i^{th}$$ digit.
2. Set `i = 0`.
3. While `num[i]` is larger than any digit after it, `++i`.
4. Find the largest digit after `num[i]`, say `num[j]` (if there are multiple largest digits, use the last one). Then swap `num[i]` and `num[j]`.

```cpp
class Solution {
public:
    int maximumSwap(int num) {
        vector<int> digits;
        map<int, vector<int>> hash;
        for(int i = 0; num; ++i){
            int digit = num % 10;
            digits.push_back(digit);
            hash[digit].push_back(i);
            num /= 10;
        }
        maximumSwap(digits, digits.size() - 1, hash);
        int val = 0;
        for(auto it = digits.rbegin(); it != digits.rend(); ++it){
            val = val * 10 + *it;
        }
        return val;
    }
    
    void maximumSwap(vector<int> &digits, int i, map<int, vector<int>> &hash){
        if(i < 0) return;
        auto it = hash.rbegin();
        if(digits[i] == it->first){
            if(it->second.size() == 1)
                hash.erase(it->first);
            else
                it->second.pop_back();
            maximumSwap(digits, i - 1, hash);
        }
        else{
            digits[it->second.front()] = digits[i];
            digits[i] = it->first;
        }
    }
};
```

### A better solution

Same idea, but better implementation. The key is to store only the last occurrence of $$i, \forall i \in \[0, 9]$$.

Credit: [Java simple solution, O(n) time](https://leetcode.com/problems/maximum-swap/discuss/107068/Java-simple-solution-O\(n\)-time)

```cpp
class Solution {
public:
    int maximumSwap(int num) {
        string digits = to_string(num);
        vector<int> hash(10); // hash[i]: the index of the last occurrence of i
        for(int i = 0; i < digits.size(); ++i){
            hash[digits[i] - '0'] = i;
        }
        for(int i = 0; i < digits.size(); ++i){
            for(int digit = '9'; digit > digits[i]; --digit){
                if(hash[digit - '0'] > i){
                    digits[hash[digit - '0']] = digits[i];
                    digits[i] = digit;
                    return stoi(digits);
                }
            }
        }
        return stoi(digits);
    }
};
```