# [C++] 3ms, O(n) time, O(n) space, DP solution

• We only need to record a position array (pos[i]) which represent the largest number index form the i position.

For instance,
input 9 8 6 3 8
pos 0 4 4 4 4
input[pos] 9 8 8 8 8

Therefore, we only need to find the first input[i] != input[pos[i]]
and swap it.

Another example
input 5 4 3 1 2
pos 0 1 2 4 4
input[pos] 5 4 3 2 2

int maximumSwap(int num) {
string numString = to_string(num);
int n = numString.length();
vector<int> dpPosition(n, -1);

int curMaxPos = n - 1;
for (int i = n - 1; i >= 0; i--) {
if (numString[i] > numString[curMaxPos]) {
curMaxPos = i;
}
dpPosition[i] = curMaxPos;
}

for (int i = 0; i < n; i++) {
if(numString[dpPosition[i]] != numString[i]) {
swap(numString[i], numString[dpPosition[i]]);
break;
}
}

return stoi(numString);
}

• @suilan0602 brilliant idea.

• very clean and easy solution!!!! thank you
we share the same idea, but your implementation is much better than me.

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.