Longest palindromic subsequence of a string

Given a string s, return the length of its longest palindromic subsequence: the longest sequence of characters you can get by deleting zero or more characters of s, keeping the rest in order, that reads the same forwards and backwards.

Interface

Unless you agree on a different interface with the interviewer, assume:

• longest_palindrome_subseq(s: str) -> int

Example

"bbbab"   ->  4    # "bbbb"
"cbbd"    ->  2    # "bb"
"a"       ->  1

Constraints

• 1 <= len(s) <= 2000.
• s holds lowercase English letters.

Clarifying questions

• Subsequence, not substring: the characters need not be contiguous?
• Do I return only the length, or the palindrome itself?
• What is the largest input I should plan for?

What a strong answer covers

• The interval recurrence: dp[i][j] is the answer for s[i..j]; if s[i] == s[j] it is dp[i+1][j-1] + 2, else max(dp[i+1][j], dp[i][j-1]); dp[i][i] = 1.
• Filling the table in the right order (by increasing length, or i from the end), O(n^2) time.
• Reducing memory from O(n^2) to O(n) with one or two rows.
• The connection to the longest common subsequence of s and its reverse.
• Tests: one character, all equal characters, no repeated characters.

Follow-ups

• Return one longest palindromic subsequence, not only its length.
• The fewest insertions that turn s into a palindrome.
• How does this differ from the longest palindromic substring, and how would you solve that one?