Longest palindromic subsequence

Length of the longest subsequence of a string that reads the same forwards and backwards.

Time O(n²)Space O(n²)Code C#

Watch it animatedStep through it, with the running line highlighted. Free with an account.

The idea

A palindromic subsequence of s reads the same forwards and backwards, so it is exactly a subsequence that s shares with its own reverse. That turns the problem into the longest common subsequence of s and reverse(s), using the same diagonal-match, take-the-better-neighbour recurrence.

Code

public static int LongestPalinSubseq(string s) {
    string rev = new string(s.Reverse().ToArray());
    var dp = new int[s.Length + 1, s.Length + 1];
    for (int i = 1; i <= s.Length; i++)
        for (int j = 1; j <= s.Length; j++)
            dp[i, j] = s[i - 1] == rev[j - 1]
                ? dp[i - 1, j - 1] + 1
                : Math.Max(dp[i - 1, j], dp[i, j - 1]);
    return dp[s.Length, s.Length];
}

Tips

Reverse the string once, then run longest common subsequence exactly as before.
The whole string is a palindrome exactly when this length equals the length of s.

In the .NET library

This LCS trick is neat but not the only way: a direct dp[i, j] = length of the longest palindromic subsequence inside s[i..j] also works, expanding outward from each centre or shrinking inward from the ends.