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