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.