Longest Palindromic Subsequence

Share

Find length of longest palindromic subsequence in string s.

Example 1
Input: s="bbbab" → Output: 4. "bbbb" is the longest palindromic subsequence.
Example 2
Input: s="cbbd" → Output: 2

Solution Approach

DP: dp[i][j] = LPS of s[i..j]. If s[i]==s[j]: dp[i][j]=dp[i+1][j-1]+2, else max of dp[i+1][j] and dp[i][j-1].

  • dp[i][j] = LPS length of s[i..j]
  • Base: dp[i][i] = 1
  • Fill diagonally: if s[i]==s[j]: dp[i][j]=dp[i+1][j-1]+2
  • Else: dp[i][j] = max(dp[i+1][j], dp[i][j-1])
  • Return dp[0][n-1]
Java
public int longestPalindromeSubseq(String s) {
    int n = s.length();
    int[][] dp = new int[n][n];
    for (int i = 0; i < n; i++) dp[i][i] = 1;
    for (int len = 2; len <= n; len++) {
        for (int i = 0; i <= n - len; i++) {
            int j = i + len - 1;
            if (s.charAt(i) == s.charAt(j)) dp[i][j] = dp[i+1][j-1] + 2;
            else dp[i][j] = Math.max(dp[i+1][j], dp[i][j-1]);
        }
    }
    return dp[0][n-1];
}
  • Time Complexity: O(n^2)
  • Space Complexity: O(n^2)