Find out the length of the longest palindromic subsequence from a string
Given a string you have to find out the length of the longest palindromic subsequence from the given string.
Input:
T Test case
T no of input string will be given to you.
E.g.
3
bghaufaght
souabbuos
sahajkhahas
Constrain
1≤ length (string) ≤100
Output:
Print the length of the longest palindromic sub sequences from that string
Example
T=3
Input:
bghaufahgt
Output:
7 (ghafahg)
Input:
souabbuos
Output:
8 (soubbuos)
Input:
sahajkhahas
Output:
9 (sahajahas)
Let there is a string str.
Now possible arrangements are:
Let, f(a,b) = length of palindromic substring from index a to index b.
Considering the above three facts:
For, str = bghaufahgt
C++ Implementation:
Output