Statement summary:

Given a string S of length N and an array L of size K. You need to find the shortest substring of S which contains K disjointed palindromes substring of size L[1], L[2]...L[K] in any order.

For example: if

S = aaappbbccccdrrr.

L = {4, 2, 3}.

Then the answer is 10 (the substring bbccccdrrr, aaappbbcccc satisfies too, but its length is 11).

Constraint:

• N ≤ 10⁵.

• K ≤ 13.

The best I can come up with is O(NK.2^K) which iterate over all position in S, consider it as the beginning of the substring and then DP with bitmask to find the end of the substring. Of course this won't fit in the TL.

I wonder if there exist some observation which will reduce the numbers of beginning position, or there is an entirely different approach that will fit in the TL.

Thanks in advanced.