Longest Palindromic Subsequence

This program finds longest palindromic subsequence using DP.

Problem Statement

Write a Java program to find longest palindromic subsequence of "bbabcbcab".

Source Code

1 public class LongestPalindromicSubsequence {
2 public static void main(String[] args) {
3 System.out.println("Eduinq Longest Palindromic Subsequence");
4 String str="bbabcbcab";
5 int n=str.length();
6 int[][] dp=new int[n][n];
7 for(int i=0;i<n;i++) dp[i][i]=1;
8 for(int cl=2;cl<=n;cl++){
9 for(int i=0;i<n-cl+1;i++){
10 int j=i+cl-1;
11 if(str.charAt(i)==str.charAt(j) && cl==2) dp[i][j]=2;
12 else if(str.charAt(i)==str.charAt(j)) dp[i][j]=dp[i+1][j-1]+2;
13 else dp[i][j]=Math.max(dp[i][j-1],dp[i+1][j]);
14 }
15 }
16 System.out.println("Length of LPS = "+dp[0][n-1]);
17 }
18 }

Program Output

Eduinq Longest Palindromic Subsequence
Length of LPS = 7

Explanation

DP table stores subsequence lengths. - Characters compared at both ends. - Together finds longest palindromic subsequence. Conclusion: Shows how to find longest palindromic subsequence using DP.

Quick Links to Explore