240. Longest Palindromic Subsequence

Why this mechanism works

Use an interval rather than two independent prefix axes. If both endpoints match, they can surround a longest palindromic subsequence of the interior. If they differ, an optimum cannot use both as its outermost pair, so discard one endpoint and take the better interval. Fill shorter dependencies before larger intervals.

State and boundaries

dp[left][right] is the optimum within the inclusive interval text[left:right+1]. Diagonal states are one; the empty interior of a matching pair contributes zero.

Protocol

1. Handle empty text.
2. Scan left indices downward.
3. Set dp[left][left]=1.
4. Scan right indices upward.
5. On matching ends use inner+2, with a zero inner for adjacent ends.
6. Otherwise use max(drop-left,drop-right).
7. Return the full interval.

Visualization

text bbbab
choose indices 0,1,2,4 -> 'bbbb'
subsequence length 4; the skipped 'a' need not remain

Python implementation

def longest_palindromic_subsequence(text):
    n = len(text)
    if n == 0:
        return 0
    dp = [[0] * n for _ in range(n)]
    for left in range(n - 1, -1, -1):
        dp[left][left] = 1
        for right in range(left + 1, n):
            if text[left] == text[right]:
                inner = dp[left + 1][right - 1] if right - left > 1 else 0
                dp[left][right] = inner + 2
            else:
                dp[left][right] = max(dp[left + 1][right], dp[left][right - 1])
    return dp[0][-1]

Worked execution

Recorded state changes after statements; L numbers refer to the solution file. Long traces are explicitly condensed.

L2 longest_palindromic_subsequence: n = len(text)
text='bbbab'; n=5

L5 longest_palindromic_subsequence: dp = [[0] * n for _ in range(n)]
text='bbbab'; n=5; _=0

L5 longest_palindromic_subsequence: dp = [[0] * n for _ in range(n)]
text='bbbab'; n=5; _=1

L5 longest_palindromic_subsequence: dp = [[0] * n for _ in range(n)]
text='bbbab'; n=5; _=2

L5 longest_palindromic_subsequence: dp = [[0] * n for _ in range(n)]
text='bbbab'; n=5; _=3

L5 longest_palindromic_subsequence: dp = [[0] * n for _ in range(n)]
text='bbbab'; n=5; _=4

L5 longest_palindromic_subsequence: dp = [[0] * n for _ in range(n)]
text='bbbab'; n=5; dp=[[0, 0, 0, 0, 0], [0, 0, 0, 0, 0], [0, 0, 0, 0, 0], [0, 0, 0, 0, 0], [0, 0, 0, 0, 0]]

L6 longest_palindromic_subsequence: for left in range(n - 1, -1, -1):
text='bbbab'; n=5; dp=[[0, 0, 0, 0, 0], [0, 0, 0, 0, 0], [0, 0, 0, 0, 0], [0, 0, 0, 0, 0], [0, 0, 0, 0, 0]]; left=4

... 31 intermediate state changes omitted ...

L13 longest_palindromic_subsequence: dp[left][right] = max(dp[left + 1][right], dp[left][right - 1])
text='bbbab'; n=5; dp=[[1, 2, 3, 3, 0], [0, 1, 2, 2, 3], [0, 0, 1, 1, 3], [0, 0, 0, 1, 1], [0, 0, 0, 0, 1]]; left=0; right=3; inner=1

L8 longest_palindromic_subsequence: for right in range(left + 1, n):
text='bbbab'; n=5; dp=[[1, 2, 3, 3, 0], [0, 1, 2, 2, 3], [0, 0, 1, 1, 3], [0, 0, 0, 1, 1], [0, 0, 0, 0, 1]]; left=0; right=4; inner=1

L10 longest_palindromic_subsequence: inner = dp[left + 1][right - 1] if right - left > 1 else 0
text='bbbab'; n=5; dp=[[1, 2, 3, 3, 0], [0, 1, 2, 2, 3], [0, 0, 1, 1, 3], [0, 0, 0, 1, 1], [0, 0, 0, 0, 1]]; left=0; right=4; inner=2

L11 longest_palindromic_subsequence: dp[left][right] = inner + 2
text='bbbab'; n=5; dp=[[1, 2, 3, 3, 4], [0, 1, 2, 2, 3], [0, 0, 1, 1, 3], [0, 0, 0, 1, 1], [0, 0, 0, 0, 1]]; left=0; right=4; inner=2

L2 longest_palindromic_subsequence: n = len(text)
text='cbbd'; n=4

L5 longest_palindromic_subsequence: dp = [[0] * n for _ in range(n)]
text='cbbd'; n=4; _=0

L5 longest_palindromic_subsequence: dp = [[0] * n for _ in range(n)]
text='cbbd'; n=4; _=1

L5 longest_palindromic_subsequence: dp = [[0] * n for _ in range(n)]
text='cbbd'; n=4; _=2

L5 longest_palindromic_subsequence: dp = [[0] * n for _ in range(n)]
text='cbbd'; n=4; _=3

L5 longest_palindromic_subsequence: dp = [[0] * n for _ in range(n)]
text='cbbd'; n=4; dp=[[0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0]]

L6 longest_palindromic_subsequence: for left in range(n - 1, -1, -1):
text='cbbd'; n=4; dp=[[0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0]]; left=3

L7 longest_palindromic_subsequence: dp[left][left] = 1
text='cbbd'; n=4; dp=[[0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 1]]; left=3

... 15 intermediate state changes omitted ...

L8 longest_palindromic_subsequence: for right in range(left + 1, n):
text='cbbd'; n=4; dp=[[1, 1, 0, 0], [0, 1, 2, 2], [0, 0, 1, 1], [0, 0, 0, 1]]; left=0; right=2; inner=0

L13 longest_palindromic_subsequence: dp[left][right] = max(dp[left + 1][right], dp[left][right - 1])
text='cbbd'; n=4; dp=[[1, 1, 2, 0], [0, 1, 2, 2], [0, 0, 1, 1], [0, 0, 0, 1]]; left=0; right=2; inner=0

L8 longest_palindromic_subsequence: for right in range(left + 1, n):
text='cbbd'; n=4; dp=[[1, 1, 2, 0], [0, 1, 2, 2], [0, 0, 1, 1], [0, 0, 0, 1]]; left=0; right=3; inner=0

L13 longest_palindromic_subsequence: dp[left][right] = max(dp[left + 1][right], dp[left][right - 1])
text='cbbd'; n=4; dp=[[1, 1, 2, 2], [0, 1, 2, 2], [0, 0, 1, 1], [0, 0, 0, 1]]; left=0; right=3; inner=0

Why the solution is correct

Singleton and empty intervals have the stated bases. For matching endpoints, an optimum can include that matching pair around an optimum interior; a solution omitting an endpoint can be adjusted to include the pair without reducing length. For unequal endpoints at least one is omitted, and the two smaller intervals cover both possibilities.

Time and space

O(n^2) time and O(n^2) auxiliary table space.

Common mistakes

A palindromic substring requires adjacency and has a different recurrence. Reading dp[left+1][right-1] before that row is complete violates dependency order.

Reasoning card

Transfer exercise

Reconstruct one palindrome by following interval decisions, storing matched endpoints on opposite sides of the output.