Can some one please explain how to solve this question ?

First of all precompute hashes of all substrings and store it in some kind of set where, hash[x][len] stores all the starting indices of all substrings having hash = x and length = len.

Binary search on the length len and for all i from 1 to n - len + 1, find the hash value x.

Check in the corresponding set hash[x][len] if there is any index greater than i + len which can be done by lower_bound in C++ and higherKey() function of TreeSet in Java.

And you are done.

Complexity : O(n^2) because of n^2 hashes precomputation.

Thanks a lot !! . Btw , does the solution accepts O(N^2) answer ?

I hope so, n = 5000.

1 Like