PROBLEM LINK:
Author: Mohammad Shahhoud
Tester & Editorialist: Hussain Kara Fallah
PROBLEM EXPLANATION
You are given two strings S and R. You may reorder the characters in the string R in any way; let’s denote the resulting string by R_r. This reordered string is valid if it contains all substrings of S, i.e. for each substring s of S (including S itself), R_r contains s as a substring.
Find the lexicographically smallest valid reordered string or determine that there is no such valid string.
DIFFICULTY:
Easy
PREREQUISITES:
None
Quick Explanation
If S is not a subset of R , there’s no answer.
Otherwise, you would need to take a subset of letters out of R which can form S (after reorder). You would be left with some letters, distribute them in lexicographical order to the left of S and to the right of S (there’s a special case in explanation check it).
EXPLANATION:
The shortest string that contains all substrings of S is S itself. This is pretty obvious.
In order to have a valid answer, R must contain S as a subset. To verify this quickly, for each letter in S check if its frequency in S is less than or equal its frequency in R.
Now in order for R_r to be valid, it must contain S as a substring, and the remaining letters can be reordered freely. So the leftover of each letter would be its frequency in R minus its frequency in S.
Now let’s form the lexicographically minimal string. Let’s start with R_r= Empty String
First, we agreed that R_r must contain S as a substring. For all letters which are less in value than S_0 (first letter of S) append them one by one to the beginning of R_r (from small to big).
Now should we append all letters equal to S_0 or not? Well that depends on S itself (this is the special case)
If the first letter in S different than S_0 is less in value than S_0 then we must append S first to our answer R_r. Otherwise, we must append all remaining instances of S_0 then append S.
Append the rest of letters to R_r (from small to big).
Let’s take as example (R="abbbcza") and (S="ba")
The leftovers after taking S as subsequence from R is ("abbcz")
- R_r=""
- Append ("a") which leads to (R_r="a")
Now notice if we append the free "b" letters first then append S we would have R_r="abbba". - But if we append S first we would have (R_r="aba")
- Append free "b" letters yielding (R_r="ababb")
- Append rest of letters concluding finally with (R_r="ababbcz")
AUTHOR’S AND TESTER’S SOLUTIONS:
EDITORIALIST’s solution: Can be found here