Finding the longest palindrome subsequence.
Here’s a Java program that finds the longest palindrome subsequence in a given string:
public class LongestPalindromeSubsequence {
public static int longestPalindromeSubsequence(String s) {
int n = s.length();
int[][] dp = new int[n][n];
// All characters in the string are considered palindromes of length 1
for (int i = 0; i < n; i++) {
dp[i][i] = 1;
}
// Finding the longest palindrome subsequence for substrings of length 2 to n
for (int len = 2; len <= n; len++) {
for (int i = 0; i < n - len + 1; 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];
}
public static void main(String[] args) {
String input = "character";
int longestPalindromeLength = longestPalindromeSubsequence(input);
System.out.println("Longest Palindrome Subsequence Length: " + longestPalindromeLength);
}
}
In this program, we use a dynamic programming approach to solve the problem. We create a 2D array `dp` to store the lengths of the longest palindrome subsequences for different substrings of the input string. The value `dp[i][j]` represents the length of the longest palindrome subsequence for the substring from index `i` to index `j` in the string.
We initialize the diagonal elements of the `dp` array to 1 because each character in the string is considered a palindrome of length 1.
Then, we iterate through the substrings of length 2 to `n` (where `n` is the length of the string) and fill in the `dp` array based on the following conditions:
– If the characters at positions `i` and `j` are the same, we increment the length of the longest palindrome subsequence by 2 and store it in `dp[i][j]`. This corresponds to adding the current two characters to the longest palindrome subsequence of the substring without these two characters (`dp[i + 1][j – 1]`) and increasing its length by 2.
– If the characters at positions `i` and `j` are different, we take the maximum of the longest palindrome subsequence lengths for the substrings without either the `i`th character (`dp[i + 1][j]`) or the `j`th character (`dp[i][j – 1]`).
Finally, the length of the longest palindrome subsequence for the entire string is stored in `dp[0][n – 1]` and returned.
In the `main` method, we provide an example input string “character” and print the length of the longest palindrome subsequence.