Given a string s, find the longest palindromic subsequence and return its length.

A subsequence is a sequence formed by deleting some characters, or none, without changing the order of the remaining characters.

Example 1:

Input:s = "bbbab"
Output:4
Explanation:One possible longest palindromic subsequence is "bbbb".

Example 2:

Input:s = "cbbd"
Output:2
Explanation:One possible longest palindromic subsequence is "bb".

Constraints:

• 1 <= s.length <= 1000
• s consists only of lowercase English letters

Approach

#

There is one particularly important observation:

The longest palindromic subsequence of string s is equivalent to the longest common subsequence of string s and its reverse s’.

To see why, any longest common subsequence of s and its reverse is a palindrome: it appears in the forward direction and in the reverse direction, and both are identical, which is the definition of a palindrome.

There also cannot be a palindromic subsequence longer than the longest common subsequence of s and its reverse. If there were one, the longest common subsequence of s and its reverse would be longer as well.

Thus, we have successfully transformed the problem into finding the length of the longest common subsequence of s and its reverse.

This makes the problem convenient to solve with two-dimensional dynamic programming. We first define the dynamic-programming table dp[n+1][n+1], reserving one extra row and column to simplify the calculation.

The meaning of dp[i][j] is the length of the longest common subsequence of the first i characters of s and the first j characters of s’.

The recurrence is also straightforward. When the two characters are equal, dp[i][j] = dp[i - 1][j - 1] + 1; otherwise, dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]).

Rust Code

#

# struct Solution;
impl Solution {
    pub fn longest_palindrome_subseq(s: String) -> i32 {
        let s = s.into_bytes();
        let n = s.len();
        let mut res = 0;
        let mut dp = vec![vec![0; n + 1]; n + 1];
        for i in 1..=n {
            for j in 1..=n {
                if s[n - i] == s[j - 1] {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                } else {
                    dp[i][j] = dp[i - 1][j].max(dp[i][j - 1]);
                }
            }
        }

        dp[n][n]
    }
}