### PROBLEM LINK:

Author: Vitaliy Herasymiv

Tester: Istvan Nagy

Editorialist: Amit Pandey

### DIFFICULTY:

Cakewalk.

### PREREQUISITES:

Simulation of brute force algorithm.

### PROBLEM:

You have a string S which consists of N uppercase English letters. You are allowed to at most once do the following process: Choose any position in the string, remove the character at this position and insert the same character back in any other place.

Find the lexicographically smallest string you can achive.

### QUICK EXPLANATION:

Generate all possible strings, and keep track of the lexicographically smallest string.

### EXPLANATION:

We can create all possible strings by removing a character at some position and adding it to other position. We will have one string for each removed and inserted positions. So overall there will be total O(n^2) such possible strings. We can implement the process of removal and additions of character at some position in O(n) time. Overall it will take O(n^2 * n) = O(n^3) time.

We just need to write a function *Modify()*, which will take input two integers i and j, and delete the j^{th} character of the given string and insert it between i^{th} and (i+1)^{th} character. *Modify()* function will generate a new string which we can get by performing the given process at most once. We can run *Modify()* function on all possible values of i and j, and report the minimum one.

Peseudo code can be given as below:

```
string lex_minimum = given_string;
for(int i = 0 ; i< given_string.length() ; i ++)
{
for(int j =0 ; j < given_string.length() ; j++)
{
temp_string = Modify(i,j);
lex_minimum = min(temp_string,lex_minimum);
}
}
print lex_minimum
```

Solving the given problem with better complexity is an interesting task, please comment if you find such solution.

### Solution:

Setter’s solution can be found here

Tester’s solution can be found here