PROBLEM LINK: ICL1904 Problem - CodeChef


Given a string S consisting only of lowercase english characters, how many strings M of length N are possible such that S can be obtained by removing a substring from M.

It is obvious that if N< = M.size() the ans will be 0 but if N>M.size(),we can derive a relation as follows.

If we put the whole string M at the beginning, we can put power(26,N-M.size()) characters at the end of the string.

Now, we also need to try to put M.size()-i characters at the beginning and i characters at the end for all 1 <= i <= M.size().

Consider a case where M=”abc” and N=5. Then for i=1 put 2 characters of string M at the beginning and 1 character of string M at the end so the new string will be "ab c".However , we previously calculated this case "abc " , so now we need to calculate only "ab c". If we put ‘c’ in the first space (third letter) we will have duplicates because we already calculated all strings that starts by "abc" so in order to ensure uniqueness, we need to let the first space be any character other than ‘c’ and for rest of the characters can be any possible character, so the number of ways will be 25 for first space multiplied by power(26,N-M.size()-1) for the rest of spaces.

This can be done for each i from 1 to M.size() so the answer for all i will be M.size() * 25 * power(26,N-M.size()-1)

The final answer will then be power(26,N-M.size()+M.size()*25*power(26,N-M.size()-1).