PROBLEM LINK:
Practice
Contest
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
4 Likes
@amitpandeykgp , I tried solving using the following approach:
Take the smallest character in the string and take it to the letfmost possible position, call this string s1
Take the greatest character in the string and take it to the rightmost possible position, call this string s2
Take the lexicographically smallest between s1 and s2.
Can you point out the fault in this logic?
I got WA
Solution link : http://www.codechef.com/viewsolution/6566723
It is wrong. Counter example: ABAA: In this case, you will print AABA, but you can make it AAAB too 
3 Likes
Please tell me where i am wrong.
link of my solution
i tried many test cases and getting right answer.
I got, i too am getting wa in above test case.
#include
#include
#include
using namespace std;
int main()
{
int max, n,m,i,brr[51],j,p,a,b;
char arr[51],temp;
scanf("%d",&n);
while(n–)
{
max=0;
scanf("%d",&m);
for(i=0;i<=m;i++){
scanf("%c",&arr[i]);
brr[i]=(int)arr[i];
}
for(i=1;i<=m;i++)
{
for(j=i+1;j<=m;j++)
if((brr[i]-brr[j])>0)
{p=brr[i]-brr[j];
if(max<p){
max=p;a=i;b=j;}
}
}
arr[a]=arr[b];
for(j=a+1;j<=b;j++)
arr[j]=(char)brr[j-1];
for(i=1;i<=m;i++)
printf("%c",arr[i]);
printf("\n");
}
return 0;
}
what is wrong with my code please explain
@dpraveen , No, my code prints AAAB only.
Link : http://ideone.com/rU6isc
Test case : BAA.
Answer should be AAB.
But your code prints ABA.
2 Likes
From my explanation , s1 will be “ABAA” and s2 will be “AAAB”. And I’m taking the lexicaographically smaller of the two
What are you doing if there many characters which are equal to the smallest one?
What will be your output for “ZAZAZA”?
In s1, Take the rightmost smallest character
In s2, take the rightmost greatest character
Please share some typical cases.
Test case : BAA.
Answer should be AAB.
Test case : ZAZA.
Answer should be AZAZ.
2 Likes
abaaza
s1 = aabaza
s2 = abaaaz
ans is aaabza 
3 Likes
I have answered to your question on forum. See there.
Thanks
Should’ve given priority to the position for s2 
i didn’t get the logic of inserting jth character between ith and (i+1)th.Please Explain.