**Disclaimer**: I wasn’t able to solve this problem during the contest despite my best efforts!

But I figured out the solution on my own today. Here are the steps involved.

Problem: Given two strings s1, s2 , We need to rearrange s2 and get s2’ such that:

- s1 is a substring of s2’ .
- s2’ is lexicographically the smallest.

**Step 1:** Create a map to break down string s1 into character and frequency.

Example: bba = {b:2, a:1}

**Step 2:** Create a map to break down string s2 into character and frequency.

Example: bbbbacc = {b:4, a:1, c:2}

**Step 3:** Compare the two maps above. Consider a key k in map1; map1[k] must be less than or equal to map2[k]. If this condition isn’t met - print “Impossible”.

**Step 4:** If the above condition is met, subtract map1 from map2. For every key k in map2; map2[k] = map2[k] - map1[k]. In the above case, the difference becomes {b:2, c:2}

**Step 5:** Create a vector of strings from the above map such that each string is a sequence of same character repeated the desire number of times. Sort this vector. In our case this becomes [bb, cc]

The tricky part (for me) starts below:

**Step 6:** Insert the string s1 into this vector at a proper place. Our s1 was bba. So where is it inserted?

Technically, as per dictionary order bba must be inserted between bb and cc

So the answer would be [bb, bba, cc]. The final output would be bbbbacc

**But this is incorrect!** - We have bbabbcc which is lexicographically smaller than bbbbacc

So how do we resolve this. I used a workaround for this. I compared bba with bbb. That is, for the purpose of comparison I made both strings equal in length.

Once I did that, I got the order as [bba, bb, cc]. This is because bba is compared not with bb, but with bbb.

Then, the final answer is outputted as bba+bb+cc = bbabbcc.

Here is the code: https://www.codechef.com/viewsolution/26852641