Write a Program in Java Programing Language to find length of the longest palindromic subsequence from an user entered String. Your Code must be Highly Optimized.
Required:
Write a Program in Java Programing Language to find the length of the longest palindromic subsequence
from a user-entered String.
Your Code must be Highly Optimized.
Approach:
Take the String from the user using the scanner class object and then for the longest length of palindromic subsequence:
Algorithm:
Set of subsequence(ABCD): __S(BC)__ , __S(BC)D, AS(BC)__, AS(BC)D
ABCD = c1mc2 ---> Representation
from the above subsequence: we can say that if the first and last character is equal then LPS(str) = 2 + LPS(middle)
if unequal then LPS(str) = max(LPS(c1m), LPS(mc2))
Coding:
Just Iterate over the 2D array and find the longest palindromic subsequence.
for further help, please see the code below with the output.
Step by step
Solved in 4 steps with 3 images
