# Maximum-Swap

Dec 11, 2017

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: The given number is in the range [0, 10^8]

int maximumSwap(int num) {
vector<int> t;
while(num != 0) {
t.push_back(num % 10);
num /= 10;
}

int k = t.size() - 1;
while(k >= 0) {
auto max = max_element(t.begin(),t.begin() + k + 1);
if (*max != t[k]) {
int a = *max;
*max = t[k];
t[k] = a;
break;
}
k--;
}

for(auto it = t.rbegin();it != t.rend();it++) {
num = 10 * num + *it;
}
return num;
}


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

LeetCodeLeetCode

Length-of-Last-Word

Contains-Duplicate-II