670. Maximum Swap

T: O(nlogn)

S: O(n)

class Solution {
    public int maximumSwap(int num) {
        char s[] = String.valueOf(num).toCharArray();
        char t[] = String.valueOf(num).toCharArray();
        Arrays.sort(t); 
        reverse(t);
        
        int replacePos = 0;
        while (replacePos < s.length && (s[replacePos] == t[replacePos])) {
            replacePos++;
        }
        if (replacePos == s.length) {
            return num;
        }        
        
        int pos = 0;
        for (int i = replacePos+1; i < s.length; i++) {
            if (s[i] == t[replacePos]) {
                pos = i;
            }
        }
        
        swap(s, replacePos, pos);
        
        return Integer.valueOf(String.valueOf(s));
    }
    private void reverse(char[] t) {
        int left = 0;
        int right = t.length - 1;
        
        while (left < right) {
            swap(t, left, right);
            left++;
            right--;
        }
    }
    private void swap(char[] s, int i, int j) {
        char temp = s[i];
        s[i] = s[j];
        s[j] = temp;
    }
}
/*
You can swap two digits at most once to get the maximum valued number.

naive thinking

replace the index 0 to biggest number in index 1~n

so 2736 => 7236

but if 27367771 => replace which one?  the lowest 7, make this 2 to smallest place

case2
but if 99234 => should return 99432

so do a desc sort to gen a new t
99234 => s[i] (origin )
99432 => t[i] (new one desc )

we can find the pos need to replace is  s[2], and we can use t[2] to find s[2+1 to end]

it's s[end]

so s[2] swap with s[end] => get 99432



if. skip until to end => return num directly => ex: 9973
9973 is sort desc already , so it's biggest

9973 => s[i] (origin )
9973 => t[i] (new one desc )

=> same ! so skip to the end

T : O(nlogn)
S: O(n)
*/