DSA Longest Palindromic Subsequence

The problem

A palindrome reads the same forwards and backwards. The longest palindromic subsequence is the longest subsequence of a string that is a palindrome.

A subsequence may skip characters. A substring may not. That one difference changes several answers in this article.

cases = [
    ("bbbab", 4),
    ("cbbd", 2),
    ("racecar", 7),
    ("abca", 3),
]
for word, expected in cases:
    print(word, "->", expected)

The first word hides the palindrome bbbb. It skips the single a in the middle. No unbroken stretch of bbbab is that long and palindromic.

Intuition: the longest palindromic substring is a different answer

The first idea searches for the longest unbroken palindromic stretch. That stretch is a substring. The problem asks for a subsequence, which may skip characters.

Skipping can only help. Every substring is also a subsequence. Some subsequences are longer than any substring, and those are the ones this idea misses.

word = "bbbab"

def longest_pal_substring(s):
    best = ""
    for i in range(len(s)):
        for j in range(i + 1, len(s) + 1):
            part = s[i:j]
            if part == part[::-1] and len(part) > len(best):
                best = part
    return best

found = longest_pal_substring(word)
print("longest palindromic substring:", repr(found), "length:", len(found))
print("answer for the subsequence problem: 4 ('bbbb')")

The substring search stops at length three. Skipping the a joins the two pairs of b letters. The answer grows by one, and the search never sees it.

Brute force: test every subsequence for the mirror test

The brute force lists every subsequence of the string. It reverses each one and compares. A subsequence that equals its own reverse is a palindrome.

It keeps the longest palindrome it finds. A string of length n has 2 to the power n subsequences, and each one gets the mirror test.

def lps_brute(s):
    best = 0
    tested = 0
    for mask in range(2 ** len(s)):
        sub = "".join(s[i] for i in range(len(s)) if mask >> i & 1)
        tested += 1
        if sub == sub[::-1] and len(sub) > best:
            best = len(sub)
    return best, tested

for word in ["bbbab", "cbbd"]:
    best, tested = lps_brute(word)
    print(word, "->", best, "subsequences tested:", tested)

Five letters force 32 mirror tests. The tests repeat the same inner stretches many times. An interval table answers each stretch once instead.

The optimal solution: grow answers over intervals

An interval is one stretch of the string between two positions. The state dp[i][j] holds the answer for the stretch from position i to position j.

This method is interval dynamic programming, called interval DP. The problem is solved for every contiguous stretch of the string, and the stretches are handled in growing order of length.

Equal end characters wrap the inner answer with two more characters. Different end characters drop the weaker end and keep the better inner answer. The table fills short stretches first, so every inner answer is ready when needed.

def interval_lps(s):
    n = len(s)
    if n == 0:
        return 0
    dp = [[0] * n for _ in range(n)]
    for i in range(n):
        dp[i][i] = 1
    for span in range(2, n + 1):
        for i in range(n - span + 1):
            j = i + span - 1
            if s[i] == s[j]:
                dp[i][j] = dp[i + 1][j - 1] + 2 if span > 2 else 2
            else:
                dp[i][j] = max(dp[i + 1][j], dp[i][j - 1])
    return dp[0][n - 1]

def lcs_len(a, b):
    m, n = len(a), len(b)
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if a[i - 1] == b[j - 1]:
                dp[i][j] = dp[i - 1][j - 1] + 1
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
    return dp[m][n]

cases = [("bbbab", 4), ("cbbd", 2), ("racecar", 7), ("abca", 3)]
for word, expected in cases:
    via_interval = interval_lps(word)
    via_reverse = lcs_len(word, word[::-1])
    print(word, "-> intervals:", via_interval, "via reversed LCS:", via_reverse, "expected:", expected, "match:", via_interval == expected == via_reverse)

Both routes agree on every case. The reversed-string route works because a palindromic subsequence reads the same in both directions. It therefore appears as a common subsequence of the string and its reverse.

Walkthrough: cbbd stretch by stretch

The walkthrough fills the intervals of cbbd in growing order. Single characters come first. Each one is a palindrome of length one.

Pairs come next, then stretches of three, then the whole string. Each new value reads only answers from shorter stretches.

word = "cbbd"
n = len(word)
dp = [[0] * n for _ in range(n)]
for i in range(n):
    dp[i][i] = 1
print("span 1 done, diagonal:", [dp[i][i] for i in range(n)])
for span in range(2, n + 1):
    for i in range(n - span + 1):
        j = i + span - 1
        if word[i] == word[j]:
            dp[i][j] = dp[i + 1][j - 1] + 2 if span > 2 else 2
        else:
            dp[i][j] = max(dp[i + 1][j], dp[i][j - 1])
    print("span", span, "done, first stretch answer:", dp[0][n - 1] if span == n else dp[0][span - 1])
for row in dp:
    print(row)
print("answer:", dp[0][n - 1])

The pair bb at positions two and three scores two. No longer stretch improves on it. The top right cell, which covers the whole string, stays at two.

Complexity

The interval table holds one cell per stretch, and a string of length n has about n squared over two stretches, so its time and space are both O(n squared). The brute force pays 2 to the power n mirror tests.

The reversed-string route fills the same order of table. It trades no extra time for its simpler rule. Both routes leave the exponential search far behind.

for n in [5, 10, 20]:
    print("length", n, "- brute subsequences:", 2 ** n, " interval cells:", n * (n - 1) // 2 + n)

At length 20 the brute force passes one million tests. The interval table holds 210 cells. The counting makes the choice plain.

Edge cases and pitfalls

The empty string has no characters to pick. Its answer is zero, and the code returns it before touching the table. A table indexed at position zero would fail there.

Confusing subsequence with substring is the standing pitfall of this problem. The first case separates them. Any method that answers three for bbbab is solving the substring problem.

def interval_lps(s):
    n = len(s)
    if n == 0:
        return 0
    dp = [[0] * n for _ in range(n)]
    for i in range(n):
        dp[i][i] = 1
    for span in range(2, n + 1):
        for i in range(n - span + 1):
            j = i + span - 1
            if s[i] == s[j]:
                dp[i][j] = dp[i + 1][j - 1] + 2 if span > 2 else 2
            else:
                dp[i][j] = max(dp[i + 1][j], dp[i][j - 1])
    return dp[0][n - 1]

print("empty:", interval_lps(""))
print("one character:", interval_lps("a"))
print("all same:", interval_lps("aaaa"))
print("no repeats:", interval_lps("abc"))
print("even palindrome:", interval_lps("abba"))
print("two different:", interval_lps("ab"))

The no-repeats row answers one. Any single character is a palindrome. Zero would mean even one character cannot be picked, which the rules allow.