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.
You can just consider two strings: one is S and the other one rev (S[1, N]). Now building the classical dp where dp[i][j] is the longest common subsequence between the first i characters of the first string and the first j of the second, would enable you to find LCS(S[1, j], rev(S[j + 1, N])) easily for each such j by simply accessing dp[j][N — j]. This method is N^2 and I doubt that there exists anything better than that.
Ah I see. It seems that I overlooked the property of the dp itself and only used the straightforward LCS. Thanks!