One of the approaches to find the Longest Palindromic Subsequence(LPS) in a string is to reverse the string and find the longest common subsequence between the original S and reversed S' strings.
I did some further research and found that it is not necessary that LCS(S,S') outputs the longest palindromic subsequence (LPS), instead the LPS is one of the all possible LCSs between S and S'.
So as long as we just have to find the length of LPS and not the LPS string itself the LCS(S,S') approach works fine. But for that it must be proved that if length of LPS is x then there exists no subsequence greater that length x common between S and S'. How do I mathematically or intuitively prove this?
Every palindromic subsequence (PS) of the string is also a subsequence. Yet reverse of PS is also itself, so it will always be the subsequence of S'.
For every longest palindromic subsequence (LPS) there must be a middle letter(s) (ML). Whereas from that going on, one takes the longest possible subsequence on the left side of S and the other takes the longest possible subsequence on the right side of S (which is the left side of S'). Yet this is the LCS algorithm, where there must be some positions that are ML where LCS of S[1..ML] and S'[1..ML] create an LPS.
Mathematically to say I think it will be something like this:
$$$\forall PS \rightarrow PS \subset S$$$
$$$\forall PS' \rightarrow PS' \subset S'$$$
$$$PS = PS' \rightarrow PS \subset S'$$$
We have $$$LPS(S) = left(S) + right(S) \Leftrightarrow LPS(S) = left(S) + left(S') \Leftrightarrow \exists p \in [1, n]: LPS(S) = LCS(S[1..p], S'[1..p])$$$
Every LPS of S will be a subsequence of (S,S'), if we assume that there exists a $$$LPS$$$ $$$of$$$ $$$S$$$ $$$of$$$ $$$length$$$ $$$>$$$ $$$LCS(S,S')$$$ then it would mean there exists a $$$subsequence$$$ $$$of$$$ $$$length$$$ $$$>$$$ $$$LCS(S,S')$$$. Hence our assumption is wrong because there shouldn't exist a $$$subsequence$$$ $$$of$$$ $$$length$$$ $$$>$$$ $$$LCS(S,S')$$$.