I solved the first two cases of this problem .Here is how i approached the problem
First i calculated the frequency of occurrence of each substring which was stored in a vector (named vec in my code) then i went on to precompute the answer for every possible test case with some dirty optimizations .
But the final part of the computation involves computing a combination which makes the complexity O(N^2)
So for the given example “ababa” my vector will contain the frequency for each substring without storing the actual substring
--- a 3 --- ab 2 --- aba 2 --- abab 1 --- ababa 1 --- b 2 --- ba 2 --- bab 1 --- baba 1
Now to calculate answer for K = 2 i will have to compute
vecC2 + vec 1 C2 + … + vec[n-1]C2 which comes to be **3C2+2C2+2C2+2C2+2C2 = 7 **
the only thing which gets changed at each step is K rest is constant, So is there any mathematical/programmatic way to calculate
func(vec,K) = vecCK + vec 1CK + … + vec[n-1]CK it in one step ?
here is my solution if you need it.