# Java O(N) solution with recursive call

• ``````class Solution {
// The idea is : find the max digit, if the max digit is not at left-most position (MSB), then we swap it with the most signicant digit.
// Saying 1798 -> max digit is 9, and swap it with the digit at left most position, and get 9718. if the max digit is equal to the left-most digit, no need to swap them and we just recursivly call to get max value out of [startIndex+1, endIndex]
public int maximumSwap(int num) {
char[] digits = Integer.toString(num).toCharArray();
maxSwap(digits, 0);
return Integer.valueOf(new String(digits));
}

// digits: MSB first
// in place update
private void maxSwap(char[] digits, int start){
if(start >= digits.length){
return;
}
char maxDigit = 0;
int maxIndex = 0;
for(int i = start; i < digits.length; i++){
// here if we have duplicate max digit, we should use the right-most digit.
// Saying 1998, we should swap the right-most 9 and get max 9918.  If we swap the first 9, we got 9198 which is not the answer.
if(digits[i] >= maxDigit){
maxDigit = digits[i];
maxIndex = i;
}
}
// if max index is at start (9354) or max value is equal to start value (9198)
if(maxDigit == digits[start]){
maxSwap(digits, start + 1);
}
else{
//swap start and maxIndex
char temp = digits[start];
digits[start] = digits[maxIndex];
digits[maxIndex] = temp;
}
}
}
``````

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