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
The DP table is built by increasing substring length, comparing characters at both ends of each range, and extending inner palindromic subsequences when the ends match, together finding the length of the longest palindromic subsequence.