Java solution based on sorting and finding indices to swap


  • 3

    The idea is to convert the string to character array and sort the digits in reverse order.
    We need to find two indices i and j, that can be interchanged to get the max number in one swap.

    The first position of digit mismatch between the sorted array and the original array gives the index i that needs to be interchanged.
    At index i, in the original array, we have the smaller number.
    At inded i, in the sorted array, we have the larger number.

    Because, the larger number can occur in multiple positions in the original array, to find the correct position of j in the original array, find the last position of the larger number in the original array.

    As an example,

    lets take "927367"
    the sorted digits are now "977632"

    The first position of mismatch occurs at i = 1.
    At index 1, in the original number we have the smaller number 2 to be interchanged.
    At index 1, in the sorted number we have the larger number 7 to be interchanged.

    But 7 also occurs at multiple positions in the original array. Becuse we are going to substitute the larger number with a smaller number, it makes sense to introduce the smaller number in the least possible poisiton from the right. Interchanging the smaller number 2 with the last 7 found in 927367, gives the correct answer = 977362.

    public static int maximumSwap(int num) {
            String str = ""+num;
            char[] originalString = str.toCharArray();
            char[] sortedString = str.toCharArray();
            // Sort the digits in reverse order
            Arrays.sort(sortedString);
            sortedString = new StringBuilder(new String(sortedString)).reverse().toString().toCharArray();
    
            int i; // Find the position of mismatch between the original and sorted string
            for(i = 0; i < str.length(); i++) {
                if(originalString[i] != sortedString[i]) break;
            }
    
            if(i == str.length()) return num; // if no mismatch, no swap needed, return the original number
            int j = str.lastIndexOf(sortedString[i]); // find the last position of the mismatching digit in the original string
    
            // Interchange digits in position i and j
            char temp = originalString[i];
            originalString[i] = originalString[j];
            originalString[j] = temp;
            
            return Integer.parseInt(new String(originalString));
        }
    

Log in to reply
 

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