Hello Everyone!
I was recently studying about suffix arrays and I found myself stuck at this problem. It would be nice if someone explains how to solve this problem.
Thanks in advance 
1 Like
Hi
Let R be the reverse of string S.
Letās build the suffix array SUF of S+R.
Let nextPos be the next position we have to fill in the resulting string (ANS).
Now letās loop over SUF.
For any index i (starting from 0) if SUF[i] >= |S| it means we are talking about a reversed prefix of S.
Otherwise we are talking about a suffix of S.
For the first case we have to check if the reversed prefix refers to characters we have already considered. If SUF[i] - |S| > |R| - 1 - nextPos we have to jump to the next i.
Otherwise, we have to put R[SUF[i] - |S|, |R| - 1 - nextPos] into ANS.
Instead, while SUF[i] refers to a suffix of S and SUF[i] = nextPos, we just have to put S[SUF[i]] into ANS. Is SUF[i] != nextPos jump to the next i.
In any case we have to decrease K by 1.
We stop when K = 0 or nextPos = |S|.
At the end if nextPos < |S| we have to choose to complete ANS with the last segment reversed or not. Just compare them.
This is my code:
https://www.hackerearth.com/submission/32117500/
Not sure if it is visible by others.
The suffix array implementation is not mine. It gives TIME OUT for some TC but i believe we could improve some implementation aspects.
2 Likes
However, the problem statement is not well written. It talks about āK consecutive substringsā but actually means āK split pointsā. Otherwise, with K = 1 the only 2 possible answers would be R or S itself.
1 Like
Hi
If you are interested in yet, I have substituted the suffix array implementation with my version and got AC.
According to the site where I got it, the previous one was O(N(logN)^2) (where N is the length of the text).
This one is O(N).
Mine give TLE on two testcases as well. I have tried all optimiziations I could think of, but on my laptop those two take around 2 seconds.
Maybe gotta build suffix array in \mathcal O (N).