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
vec[0]C2 + 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) = vec[0]CK + vec 1CK + … + vec[n-1]CK it in one step ?
I don’t think there is any clever mathematical way to do this in one step because the vec[i] values are determined by each string uniquely and there’s no way to predict them.
However an optimization is that instead of storing values for each substring in vec[i], store the number of substrings that occur exactly k times in a vector.
Meaning vec[k] = number of substrings that occur exactly k times.
Then simply calculate :
In doing so you reduce the complexity of func(vec,k) from O(n^2) to O(n).
Even if you make use of this optimization, I don’t think your solution will pass as you are using a map which’ll make the complexity for generating vec[], O(n^2lgn) but I’m not too sure about it.
EDIT : Your call to s.substr() makes the complexity 0(n^3) and so your solution will definitely not pass. I suggest you use some other method as described in the editorial.