# 670. Maximum Swap

T: O(nlogn)

S: O(n)

```java
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)
*/
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://timmybeeflin.gitbook.io/cracking-leetcode/greedy/670.-maximum-swap-1.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.