[Java] Longest palindromic subsequence

Given a string, find the longest palindromic subsequence it contains.

A non palindromic string, still contains a palindromic subsequence, as a single character is a valid palindrome.

If a string contains a palindromic subsequence, there will be some characters that appear in a certain order on both sides of the middle element of the palindrome (either a single character for odd length palindromes or the space in between two characters for even length palindromes).

For example:

acca, acfca are palindromes

acbgca contains more palindromic subsequences, the longest being acbca or acgca

abccga contains more palindromic subsequences, the longest is acca

For any given palindromic subsequence, we must find the same characters in the same order on both sides of the middle point in the original string.

If we reverse the original string in O(N) time, we can then use our logic to find the longest common subsequence to find this palindrome in O(MN) time and space, which in this case is O(N^2).

Example:

abccga reverses to agccba

And the longest common subsequence to both is acca

asd reverses to dsa

and the longest common subsequence to both is any single character

You can check my implementation of longestPalindromicSubsequence on my Gist along with some tests in LongestPalindromicSubsequenceJTests.