4.A palindrome is a
nonempty string over some alphabet that reads the same forward and
backward. Examples of palindromes are all strings of length 1,
civic, racecar,
abba,…
Give a DP algorithm to find the longest palindrome that
is a subsequence of a given input string. What is the running time
of your algorithm? (40 points).
•Examples:
•Given the input “character”, your algorithm should return
“carac”.
•Given the input “TTATGTGAT”, your algorithm should return
“TATGTAT”
Python Code only