Hello , i came across the problem the problem statement is like this.
You are given a string S and you have to find minimum index j LCS(S[1, j], rev(S[j + 1, N])) is maximum, where lcs is longest common subsequence between two strings.
My approach :- firstly i tried to find lcs for every index which will be O(n^3). Then i tried to find length of Longest Palindromic subsequence of a string. let val=length of Longest Palindromic subsequence. So my final answer will be floor(val/2). Now to find a minimum j i backtrack and find what lps is and then according to that j will be retured. The problem which i faced was i was able to find length correctly for pre test cases but index was not minimum , as there can be more than one lps in string. now my question is whether my approach of finding lps length is correct or not ? and please suggest some good approach to find solution for this question ?
i am not able to see that question now so , i can not share the link.
Would this approach work?
First, reverse the string S and call it string B. Calculate all values for dp[prefix of S][prefix of B] = longest common subsequence of [prefix of S] and [prefix of B]. You can calculate this in O(N^2).
Then, you loop through all prefixes of S and prefixes of B where S and B do not intersect and find the maximum length. If there are multiple states that have the maximal answer, then choose the state where the length of the prefix of S is minimal.