Given a string **s** of length **n**, it consists of lowercase English alphabets.

The task is to **choose any two characters** in the string and replace all the occurences of the first character with the second character and the second character with the first character so that the final string is the **lexicographically smallest string** that can be obtained by doing this operation at most once.

For example, "abc" is lexicographically smaller than "bac" because 'a' comes before 'b' in dictionary order.

**Input:** s = "zyxwvu", n = 5

**Output:** "uyxwvz"

**Input:** s = "baab", n = 4

**Output:** "abba"

## Solutions

### Method 1: In O(n^2) time and O(1) space

In this approach, we need to find two characters such that the **left character (c1)** should be greater than the **right character (c2)** and "c2" should not exist left to "c1".

The idea is to iterate over the array from **i to n-2** and for each element **c1 = arr[i]** check if any element **c2 = arr[i+1...n-1]** fulfils the following conditions:

**1)** The element c2 should be smallest in sub-array (i...n-1).

**2)** The element c2 should not exist in sub-array (0...i-1).

If any value is found for **c2**, iterate over the array again and replace **c1** with **c2** and **c2** with **c1**.

##### Complexity

The time complexity of this solution is **O(n^2)** and space complexity is **O(1)**.