# PythonThe longest palindrome sequence

#### Hilton D

##### Coder
A palinadrome is a nonempty string that reads the same forward and backward across some alphabet. Palindromes include all strings of length one, civic, racecar, and aibohphobia (fear of palindromes). Provide an efficient approach for determining the longest palindrome that is a subsequence of the supplied input string. Given the input "character," your algorithm should return "caac."
Code:
``````def mylongest(self, i, j):
if j - i <= 1:
return j-i
else:
if self.sequence[i] == self.sequence[j]:
return self.mylongest(i+1,j-1) + 2
else:
return max (self.mylongest(i+1, j), self.mylongest(i, j-1))``````
I now understand how to calculate the length of the result. How can I obtain the result sequence? I'm checking all 2n combinations; according to this source, it's the least efficient algorithm, and it recommends using a dynamic program to solve this problem in O(n2), is that correct?

A palinadrome is a nonempty string that reads the same forward and backward across some alphabet. Palindromes include all strings of length one, civic, racecar, and aibohphobia (fear of palindromes). Provide an efficient approach for determining the longest palindrome that is a subsequence of the supplied input string. Given the input "character," your algorithm should return "caac."
Code:
``````def mylongest(self, i, j):
if j - i <= 1:
return j-i
else:
if self.sequence[i] == self.sequence[j]:
return self.mylongest(i+1,j-1) + 2
else:
return max (self.mylongest(i+1, j), self.mylongest(i, j-1))``````
I now understand how to calculate the length of the result. How can I obtain the result sequence? I'm checking all 2n combinations; according to this source, it's the least efficient algorithm, and it recommends using a dynamic program to solve this problem in O(n2), is that correct?
My first question:
Are you required to output the length of the longest palindrome, or the actual string of the palindrome?