This Java program solves the problem of finding the longest palindromic subsequence in a given string using dynamic programming. The goal is to compute the length of the longest subsequence that is the same when read forwards and backwards.
Java Program
public class LongestPalindromicSubsequence {
// Function to find the length of the longest palindromic subsequence
public static int longestPalindromicSubseq(String str) {
int n = str.length();
// DP table where dp[i][j] represents the length of the longest palindromic subsequence
// in the substring str[i..j]
int[][] dp = new int[n][n];
// Base case: A single character is always a palindrome of length 1
for (int i = 0; i < n; i++) {
dp[i][i] = 1;
}
// Build the dp table in a bottom-up manner
for (int len = 2; len <= n; len++) {
for (int i = 0; i < n – len + 1; i++) {
int j = i + len – 1;
if (str.charAt(i) == str.charAt(j)) {
dp[i][j] = dp[i + 1][j – 1] + 2; // Characters match, add 2
} else {
dp[i][j] = Math.max(dp[i + 1][j], dp[i][j – 1]); // Characters don’t match
}
}
}
// The value in dp[0][n-1] contains the length of the longest palindromic subsequence
return dp[0][n – 1];
}
public static void main(String[] args) {
String str = “BBABCBCAB”;
// Find and print the length of the longest palindromic subsequence
int result = longestPalindromicSubseq(str);
System.out.println(“Length of the longest palindromic subsequence is: ” + result);
}
}
Explanation of the Program Structure
This program finds the longest palindromic subsequence in a given string using dynamic programming. A subsequence is a sequence derived from another string by deleting some or no characters, and a palindromic subsequence is one that reads the same forwards and backwards.
- longestPalindromicSubseq function: This function computes the length of the longest palindromic subsequence in the input string. It uses a dynamic programming table
dp[i][j]to store the length of the longest palindromic subsequence in the substringstr[i..j]. - Dynamic Programming Table (dp): The 2D table
dp[i][j]is filled based on whether the characters at positionsiandjmatch. If they match, the length of the palindromic subsequence is increased by 2. If they don’t match, the length is the maximum of ignoring either the character atiorj. - Main logic: The program builds the DP table in a bottom-up manner by considering substrings of increasing lengths. For each substring, it checks whether the characters at the ends match, and updates the table accordingly.
- Base case: The base case is when a substring consists of a single character, which is always a palindrome of length 1. This is handled by initializing
dp[i][i] = 1for alli. - main function: This function initializes a sample string, calls the
longestPalindromicSubseqfunction, and prints the length of the longest palindromic subsequence.
Step-by-Step Process:
- We initialize a dynamic programming table
dpof size(n x n), wherenis the length of the string. Each entrydp[i][j]stores the length of the longest palindromic subsequence in the substringstr[i..j]. - We start by filling the table for substrings of length 1 (which are always palindromes of length 1), then for substrings of length 2, and continue to build up the solution for the entire string.
- If the characters at the current positions
iandjmatch, we add 2 to the value in the diagonaldp[i+1][j-1]. If they don’t match, we take the maximum of ignoring either character. - The final result is stored in
dp[0][n-1], which represents the length of the longest palindromic subsequence for the entire string.
Example:
Consider the following string:
str = "BBABCBCAB"
The longest palindromic subsequence in this string is “BABCBAB”, and its length is 7. The program will output:
Length of the longest palindromic subsequence is: 7
Conclusion:
This Java program efficiently solves the problem of finding the longest palindromic subsequence using dynamic programming. The time complexity of this solution is O(n^2), where n is the length of the input string. This ensures that all possible subsequences are explored, providing an optimal solution.
