Longest Palindromic Subsequence
Problem
Given a string s, return the length of its longest palindromic subsequence: the longest palindrome you can get by deleting any characters from s while keeping the rest in their original order. The kept letters do not need to be next to each other in s.
Examples
Input: s = "character"
Output: 5
Why: "carac" keeps c, a, r, a, c in order and reads the same both waysInput: s = "abcd"
Output: 1
Why: no letter repeats, so a single letter is the bestInput: s = ""
Output: 0
Why: edge case, nothing to keepHints
0 / 3
A palindrome reads the same in both directions, so a palindromic subsequence of s is also a subsequence of s written backwards.
That turns the question into one about two strings, s and its reverse. What is the longest sequence that appears in both, in order?
Compute the longest common subsequence of s and reversed s with the usual table: equal letters extend the diagonal value by one, otherwise take the larger of the value above and the value to the left. Keeping only the previous row is enough.
Solution
Every palindromic subsequence of s is also a subsequence of its reverse, so it is common to both strings; in the other direction, a longest common subsequence of s and its reverse can always be chosen to be a palindrome, so the two lengths are equal. The standard recurrence fills a table whose cell (i, j) holds the answer for the first i letters of s and the first j letters of the reverse. Each row only reads the row above it, so two rows of length n + 1 are enough. Time is O(n²) and space is O(n).
def longest_pal_subseq(s):
rev = s[::-1]
prev = [0] * (len(s) + 1) # the row for zero letters of s
for a in s:
cur = [0]
for j, b in enumerate(rev):
# a match extends the diagonal; otherwise keep the better neighbour
cur.append(prev[j] + 1 if a == b else max(prev[j + 1], cur[j]))
prev = cur
return prev[-1]
print(longest_pal_subseq("character")) # -> 5
print(longest_pal_subseq("abcd")) # -> 1
print(longest_pal_subseq("")) # -> 0Stuck on the idea rather than the code? Longest Common Subsequence covers it.