All Substrings - Binary Search logic

help
1

Hello can anyone tell me what is wrong with my code CodeChef: Practical coding for everyone

The logic i used is sort r and find each character of s in using binary search and erase those characters. if not found impossible else insert s in r just where s[0]>r[i]. It would be helpful if anyone could point out the flaw. Thank you!

2

Wrong :frowning_face:

  1. You can’t use any sorting as it would lead to tle.
  2. You also need to print the lexicographically smallest string possible.
  3. Make some cases like if (s = ddac, and r = bcacbaddd. && s = ddac and r = bcacbadd)
3

Thanks for looking into it but I saw some successful solutions using sorting so AFAIK tle(I dont end up having tle) is not a problem and to get the lexicographically small i place s in the most favourable position.
Can you give me the right answer to the cases you prescribed?

4

Consider this testcase:
ddfg
becacbadddfg
Your output: aabbccddfgde
Correct output: aabbccdddfge
Key point: Between aaba and aaab. second one is lexically small.

And I have used your code and made some changes but I still got TLE for last test case, so sorting would definitely get TLE.

You can go through my solution : https://www.codechef.com/viewsolution/26857882

1 Like
5

Thank you bro! understood.

1 Like