ALLSUB Editorial

PROBLEM LINK:

Practice
Contest

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

7 Likes

missed the special case…nice problem

cook your dish here

for _ in range(int(input())):
s = str(input())
t = str(input())
ds , dt ,ans ,flag = {},{},"",1
for i in s:
if i in ds.keys():ds[i] += 1
else:ds[i] = 1
for i in t:
if i not in dt.keys():dt[i] = 1
else:dt[i] += 1
for i in ds.keys():
if i not in dt.keys():
flag = 0
break
elif ds[i]>dt[i]:
flag = 0
break
else:
dt[i] -= ds[i]
if flag==0:print(“Impossible”)
else:
if len(s)==len(t):print(s)
else:
res = []
for i in dt.keys():
for j in range(dt[i]):res.append(i)
res.sort()
for i in range(len(res)):
if res[i]<s[0]:ans = “”.join(str(res[i])+ans)
else:break
ans += str(s)
for j in range(i,len(res)):ans += str(res[j])
print(ans)

Can anybody please help me why am i gettting a WA here?

Special case made the question awesome.