All Substring Explanation!

I’ll explain this question as simple as possible. Make sure you check the code.It’s Full of comments to help you see what each line is doing.

Problem : ALLSUB
Solution : Code

In this question, We have been given two Strings S and R.

And we have to find the lexiographically smallest *Valid* string by reordering the characters of String R.

Now the first question is.

What is a valid string?

According to question a valid string is one which has all substrings of S , including S.

Now it’s clear that the reordered string must have S intact, and it should be formed by using all the characters of R.

So We first create a frequency map of R which maps each character to its frequency in String R.

The we do the same for S.

Now if there is a situation in which the frequency of some character in frequency map of R is less than that of S, then there is no way you can form the valid string as you’ll run short of letters and won’t be able to form S in new string.

So that’s our condition for outputting "Impossible".

Since we have to keep S intact in new string, we would be only able to use the left letters after all letters reserved for S is gone.

Now you can create a string called 'left' and keep these remaining letters.

now all the letters smaller (lexiographically) than the first character of S would go on the left side of S and bigger would go on right of S.

There is one case when they both become equal. In that case, we can simply generate both possibility and choose the smaller (lexiographically).

Done !

The code speaks for itself. You can check it. If you have any confusion, tell me

7 Likes

Support,the solution is very concise and straightforward.

2 Likes

Finally someone who doesn’t over complicate stuff. This is how editorials should be!
Good Job man!

1 Like

Thanks much bro

20 char

2 Likes

Very nice explanation

1 Like

I did the exact same thing, but I am getting a WA. Please provide a counter test case. Help appreciated. https://www.codechef.com/viewsolution/26842648

Can someone give a counter testcase for my answer. I pretty much did the same thing as explained above
https://www.codechef.com/viewsolution/26854719

@sauravshah
Your Program fails for this test

1
cat
catc

ccat

Expected Output

catc

@res_req_ted
Your Program fails for this test

1
cat
catc

ccat

Expected Output

catc

My program’s output is catc itself.

@sauravshah Sorry bro i opened someone elses i think

1
ba
abba

Expected Output

abab

Yours

baab

Ahh! I got that. Thanks

1 Like

nyc one,very simple and easiest one upto this time…one thing lots of people doing mistake that how the middle of the final string R will be merged with S,so that it will be lexicographically small…So, u cleared that doubt.Thanks for this

1 Like

Thanks a lot for the well-explained code. I was struck on this problem for 2 hours.

1 Like

Can someone please tell me where my code goes wrong . I did the same thing as explained above.https://www.codechef.com/viewsolution/26858157

nice explanation brother!!!

1 Like

Very good Explanation indeed. My approach for this ques was almost the same but still i am getting WA. As i am fairly new to CodeChef or CP to be exact i don’t know how to find counter cases for one’s program. Can anyone be kind enough to give some insight upon the wrong Testcases? Thanks in advance.
https://www.codechef.com/viewsolution/26889606

1 Like

Please correct me ,give me counter case,
https://www.codechef.com/viewsolution/26890345

1
cppt
acptp