I don’t know what happened to me last night not to solve this.
Now I see my mistake the inner for loop should be 0<= j < n
hey what about this approach get the ascending order of given string compare the sorted string one by one and then the first character that differs in given string then that of sorted one is inserted in and we remove the last occurence of that character.
please suggest if any correction my code is this CodeChef: Practical coding for everyone but giving wrong answer
@dpraveen I tried exactly what u said… Correct me if i am wrong.
http://www.codechef.com/viewsolution/6570234
Here is my code . I tried an algorithm similar to selection but all I got was WA. I would be glad if anyone can help me in debugging
To insert character use str.insert() and REMEMBER to erase that character before inserting.Use str.erase().Also when using str.erase please use the position parameter as well as iterator parameter(here it is 1).
O(n*n)
Take every character and assume rest is sorted and insert this char in an appropriate position,lexicographically compare with the given string and then find out the minimum one
Code in Python : CodeChef: Practical coding for everyone
Still not able to figure out why my answer is wrong. Please provide some test cases.
#include<iostream>
#include<string.h>
using namespace std;
int main()
{
//cout<<strcmp("fff","ddd");
int t,i,j,k,len;
char str[52],temp[52],chr,min[52];
cin>>t;
while(t--)
{
cin>>len>>str;
strcpy(min,str);
for(i=0;i<len;i++)
{
chr=str[i];
for(j=0;j<len;j++)
{
strcpy(temp,str);
if(i==j)
continue;
else if(i<j)
{
for(k=i;k<j;k++)
{
temp[k]=str[k+1];
}
temp[k]=chr;
}
else
{
for(k=i;k>j;k--)
{
temp[k]=str[k-1];
}
temp[k]=chr;
}
//cout<<temp<<endl;
if(strcmp(temp,min)==-1)
strcpy(min,temp);1
}
}
cout<<min<<endl;
}
return 0;
}
nice editorial… thanks for posting
Someone please help.
Please someone give me a test case on which my solution fails.
Here is my code.
http://www.codechef.com/viewsolution/6574661
Anyone wanna help me find out counter example for my code to the problem?
http://www.codechef.com/viewsolution/6574368
i can be done in o(n).
lets take an example -abaaazzaa
alright now lets calculate frequency of all letters.(do it in ha table or something)
a-6,b-1,z-2
alright now , we store the leftmost a’s position that is 8(i=0 based index).
so its obvious that at index 1 , we need to replace b with a, which can be done in two ways.
1st way- we take the last a and inject it before b.
2nd way- we keep shifting b towards the end until there is a letter which is bigger than b.
the key obs is that , the answer has to be one of it , there is no other option, so what we do is buid both the string seperatly (both are o(n)).
now s1=aabaaazza and s2=aaaabzza
so the answer is s2.
if there is any cornor case im missing , pls lemme know 
@amitpandeykgp i solved this question using C++ stl ( insert and erase function).I just want to know whether complexity of insert and erase is O(1) or O(n)?? Here is my solution :
https://www.codechef.com/viewsolution/10649315
So, overall Complexity is O(n^3) or O(n^2) ??
all test cases given above are working then also i am getting a wrong ans
https://www.codechef.com/viewsolution/10858733
help!
can anyone provide me some test cases
i think my approach is o(n)
link:CodeChef: Practical coding for everyone
with two steps :
first insert at first mismatch
second: remove at first mismatch
and than compare both solution and print that which is lesser
It is wrong. Counter example: ABAA: In this case, you will print AABA, but you can make it AAAB too
3 Likes
@dpraveen , No, my code prints AAAB only.
Link : rU6isc - Online C++ Compiler & Debugging Tool - Ideone.com
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?