Longest Palindromic Subsequence

Problem

Return the length of the longest palindromic subsequence of s, where characters need not be contiguous.

Use interval dynamic programming: matching end characters add 2 to the inside answer, otherwise the best drops one end. An empty string gives length 0.

Hint

Fill intervals by increasing length so the inside interval is always ready.

Test cases

case 1

in: ["bbbab"]

expected: 4

case 2

in: ["cbbd"]

expected: 2

case 3

in: [""]

expected: 0

case 4

in: ["a"]

expected: 1

case 5

in: ["abcabcabc"]

expected: 5

Starter codePython

def longest_palindromic_subsequence(s):
    # Your code here
    pass

5 test cases · run your code against them in the editor