How to solve this prblem(CHSTR) mathematically , need help with summation involving a factorial ?

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 ?

here is my solution if you need it.

Thanks

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 :

func(vec,k) = vec[k] * kCk + vec[k+1] * k+1Ck + … vec[n] * nck

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.

1 Like

My o(n^2) solution with a larger constant didn’t work ,so I doubt that o(n^2 logn) would work.