Return the length of the longest subsequence of s that is a palindrome. A
subsequence keeps order but may drop characters.
maxPalindromicSubsequence(s)
Input format: a single string.
"luwxult" // → 5 ("luxul")
"xyxz" // → 3 ("xyx")
"a" // → 1
A palindrome's first and last characters must match, which points to defining the subproblem on a range [i, j] rather than a prefix or single index. Ask: what's the longest palindromic subsequence within that range?
If the end characters match, both can be in the palindrome (one at each end), contributing 2, plus whatever palindrome fits strictly between them: 2 + best(i+1, j-1). If they differ, at least one can't be an outer pair for the whole range, so take the better of dropping the left end or the right: max(best(i+1, j), best(i, j-1)).
A single character is a palindrome of length 1. A range where left has passed right (empty) contributes 0.
Many different sequences of "drop left" / "drop right" decisions land on the same (i, j) range. The naive approach recomputes the best length for that range every time, even though the answer never changes. This grows exponentially with string length.
The best length for a range depends only on its endpoints i and j — not on how the recursion narrowed to it. This is interval DP: the state is a contiguous interval, and larger intervals build from smaller nested ones.
Cache keyed by (i, j). Check before recursing; otherwise apply the match/mismatch logic, store, return.
O(n²) distinct (i, j) pairs for a string of length n, each computed once at constant cost given cached sub-ranges — O(n²) total instead of exponential. Interval DP reappears whenever a problem's structure depends on matching or splitting a contiguous stretch.
def max_palindromic_subsequence(s):
memo = {}
def best(i, j):
if i > j:
return 0
if i == j:
return 1
key = (i, j)
if key in memo:
return memo[key]
if s[i] == s[j]:
res = 2 + best(i + 1, j - 1)
else:
res = max(best(i + 1, j), best(i, j - 1))
memo[key] = res
return res
return best(0, len(s) - 1)
Sign in to join the discussion.
No comments yet. Be the first to ask a question.
Press Run to execute your code, or Submit to test and complete this problem.