670. Maximum Swap

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, 108]

// Brute Force
int maximumSwap(int num) { // time: O(n^2); space: O(n)
    string str = to_string(num);
    int res = num, n = str.length();
    for (int i = 0; i < n; ++i) {
        for (int j = i + 1; j < n; ++j) {
            swap(str[i], str[j]);
            res = max(res, stoi(str) );
            swap(str[i], str[j]);
        }
    }
    return res;
}

int maximumSwap(int num) { // time: O(n); space: O(n)
    vector<int> last_pos(10, -1); // last occurrence position of digits
    string str = to_string(num);
    int n = str.length();
    for (int i = 0; i < n; ++i) last_pos[str[i] - '0'] = i;
    for (int j = 0; j < n; ++j) {
        for (int k = 9; k > (str[j] - '0'); --k) {
            if (last_pos[k] > j) {
                swap(str[j], str[last_pos[k]]);
                return stoi(str);
            }
        }
    }
    return num;
}

// Optimized Solution
int maximumSwap(int num) { // time: O(n); space: O(1)
    string str = to_string(num);
    int n = str.length(), pos1 = -1, pos2 = -1, mx_pos = n - 1;
    for (int i = n - 2; i >= 0; --i) {
        if (str[i] < str[mx_pos]) {
            pos1 = i;
            pos2 = mx_pos;
        } else if (str[i] > str[mx_pos]) {
            mx_pos = i;
        }
    }
    if (pos1 != -1) swap(str[pos1], str[pos2]);
    return stoi(str);
}