I'm trying to solve MKTHNUM on SPOJ using Wavelet Tree Data structures from rachitjain's blog

Here is my code: http://ideone.com/BMZqj0

Unfortunately, I keep getting RTE on large test cases.

However, I have also tested my solution on this problem with the exact same code (only differs in use of test cases) and it got accepted on that problem.

Can anyone tell why my solution getting RTE on SPOJ while getting accepted on other OJ?

P.S. I also got RTE on KQUERY problem using the same data structure.

Thanks.

Defining substring For a string P with characters P1, P2 ,…, Pq, let us denote by P[i, j] the substring Pi, Pi+1 ,…, Pj.

Given a string S with small alphabet characters S1, S2 ,…, SN, return an array with two elements. First is the smallest j (1 ≤ j < N) for which LCS(S[1, j], rev(S[j + 1, N])) is maximal and second is the maximal value of LCS(S[1, j], rev(S[j + 1, N])). Here, rev(A) denotes reverse of string A.

For example,

S="abba"

LCS(S[1, 1], rev(S[2, 4])) = LCS("a", "abb") = 1

LCS(S[1, 2], rev(S[3, 4])) = LCS("ab", "ab") = 2

LCS(S[1, 3], rev(S[4, 4])) = LCS("abb", "a") = 1

Hence, we return [2, 2].

What I have done so far is finding a O(N^3) algorithm which is done by trying all i (1<=i<n) and find lcs of both strings. How can we reduce the time complexity ?

P.s. This was an interview question so there's no constraint on the string length and time limit. Just wondering how to improve the algorithm.