Hello there,

I was trying to solve this problem on Hackerearth the problem asks for the length of **the longest substring** which is repeated at least **K** times, **1 <= K <= |S| <= 10^6**

I built the suffix array of the string and built the LCP array then get the maximum element among the minimum elements in all possible consecutive segments of length **K-1** in the LCP array, Thus, if the LCP array was **[0,1,2,3,2,3]** and K was **4** then we have :

1. [0,1,2] min is 0

2. [1,2,3] min is 1

3. [2,3,2] min is 2

4. [3,2,3] min is 2

Now the maximum element is 2 and this is the answer, My solution keeps getting WA on some test files, and unfortunately editorial page has no explanation about the solution, just two codes, one uses an absolutely different idea where it uses hashing and binary search (No idea!!) and the other one slightly uses the same idea using suffix tree instead but it's so messy and couldn't track it down.

Here's my code .

Any help would be highly appreciated .

3 12

abcdefabcdea

I think you should not use a set to find the sliding window maximum. maybe use a monotone queue instead.

UPD: I am not quite sure about the output, please notify me in case my test case produces correct answer.

My previous code outputs

4where the the correct output is1.I was stupidly using the set to get the sliding window maximum where I was erasing the minimum element in each step instead of erasing the first element of the segment .

I used a segment tree and got AC in 15 seconds :D .

Now I modified the first code and got AC without a segment tree and it passed even faster :D . (13 seconds)

Thanks so much CantGetAnyACWhyAmISoWeak I do appreciate your help .

Just out of curiosity, I have no idea how to do that using a monotone queue, it would be great if you could enlighten me .

Monotone queue is somehow standard solution towards sliding window. It gets all the sliding window max/min in O(N) total. Maybe this article would help you (http://abitofcs.blogspot.hk/2014/11/data-structure-sliding-window-minimum.html). I'm very poor in conveying ideas, so I'll just leave it here ;>

Auto comment: topic has been updated by yashi (previous revision, new revision, compare).