### 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