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).