Hey guys! I have tried solving this question with a brute approach but I couldn’t do it. Please share your code or approach with this problem. Thanks in advance
Nvm the date on the bottom right is 29th.
You thought it is an on-going contest?
Dude… you have any idea how to solve?
@shravan660
for K=1 , output the given string.
for K=2, start from 1st index , for an index 'i' , if you find a character in range [i+1,N] which is smaller(smallest) than a[i], then swap a[i] with a[j] , if there are multiple such smallest characters in the range , then swapping a[i] with a[j] where “j” is the largest possible index is the most optimal thing to do.
for K=3, do the same as you did for K=2 , but for your newly found index 'j' , find a character greater than a[j] in range [i+1,j] and let it have index “r”. Go for the smallest such “r” and swap a[j] with a[r] . If you don’t find it, you can check for an index > j , if it has a smaller(smallest) character,then swap a[index] with a[j].If even this does not happen, then do nothing.
for any large “K”, do the exact same process you did for K=2 , and mark all your favourable indices, if the count of favourable indices become(=K) , then, stop and just sort the characters which are in those favourable spots, but if count==K+1, then go back to count=K-1 ,and do the exact same thing we did for K=3 .
You can do it in O(N^2) , also in O(N.logN) or O(N)
Lets take a complicated test-case : -
bcdgafsfdterf
What is the best string we can get ?
It is : abcddefffgrst
(There are many cases in this problem which you need to consider)
Lets try to achieve the string which will have “abc” in the start , so the favourable indices will be :- {1,2,3} and {5} , lets sort these guys : - {b,c,d} and {a}–> {a,b,c} and {d}
,
hence the final string will be : - abcgdfsfdterf
Hence, with K=4, we can achieve the final string having “abc” at the start. There are FEW very strong conditions to take care of :-
1)When counting the favourable guys , if for a particular character , guys on left>guys on right , subtract them. Also, if ater sorting , a character occurs at the the same position , then you don’t count it in K.
2)Say,you reach k-1 and k+1, but not “k”, then you have to do some special step(K=3) I mentioned above . 
2 Likes
Thanks a lot broooo:fire:
@anon55659401 If I got you right, this will not work. Simple test case for K=2:-
cab
Your approach will give - bac
Correct ans - acb
We need to find “smallest” character ( maybe you wanted to say smallest instead of smaller) in range [i+1,n) and swap with it. If more than one smallest character are there only then we will choose the character at greater index. for eg. consider caba
correct output - aabc
I meant “smallest” only , I did not edit it cuz I thought , the reader would understand automatically as the lexicographically smallest string can only be achieved if we swap with the smallest guy having largest index.
Let me update it now…
Applying your approach for K=3 also doesn’t work on test case “cab”. After applying K=2 string becomes acb. Then there is no greater character in range [i+1, j]. But correct ans is abc. I don’t think this approach generalises.
I didn’t write everything in the solution cuz I was busy at the given time. Now, I have updated my solution.
And yea, I got AC in this problem in the contest
1 Like
Thanks for updating. That was really misleading.
1 Like
This problem is just too complicated, Man . Writing its complete solution in normal words is next to impossible. I would like to say , that I haven’t explained what to do if a guy directly goes from k-1 to k+1 , because its too complicated to explain , so let the reader do the hardwork
By any chance, could you post your code? I tried to do it, but couldn’t get it to O(nlogn) or below. It’s fine if it’s a bit obfuscated, I’ll figure it out.
Hackerearth test system is very bad, I was forced to write the code in their compiler and no change of tab was allowed. Nor did the Hackwithinfyi guys allow for copy-paste option, so when I submitted the test, it was all gone. I will write the full clean code again.
Also, I think this problem is of much higher level for a short contest conducted by a company like Infosys . They must have copied it from somewhere 
Its Ok to solve it, but explaining it is really hard.
2 Likes
You’ll write the full clean code again? Thanks a lot. I struggle a lot with these kind of questions, so I’m grateful to you for helping.
1 Like
Hey, I used maps in this question, so even my solution was O(nlogn)
Well, a person whom you know is my friend, so why not!
1 Like
I do? I kinda feel bad for not knowing who you are now.
1 Like
Could anyone provide the link to the problem?
are u in third year bro ?