All Substring (Unofficial) Editorial

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:

  1. s1 is a substring of s2’ .
  2. 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

2 Likes

:+1::+1::+1:
20 char

Nice Explanation…!

Nice…:ok_hand::ok_hand::ok_hand: 20 char

bro can u check where my code is failing …I did exactly what u write in your editorial…Here is link to my code https://www.codechef.com/viewsolution/26855560


You may check this out. Hope it helps. :slightly_smiling_face: