The problem. Given a string s, return the length of its longest palindromic subsequence — letters taken in order, not necessarily next to each other, that read the same forwards and backwards.
![The table dp[i][j] for s = bbbab, with i down the side and j along the top. Each cell is the longest palindromic subsequence inside s[i..j]; the diagonal is 1 and cells below it are empty. The top-right cell, dp[0][4], is 4: s[0] and s[4] are both b, so they wrap the best answer inside, dp[1][3] = 2, giving 2 + 2 = 4, the subsequence bbbb.](/drawings/30be573c-0316-413e-92a3-8b2e7c14d80b.svg)
s = "bbbab" -> 4 ("bbbb")
s = "cbbd" -> 2 ("bb")
s = "racecar" -> 7 (the whole string)
s = "abcd" -> 1Some problems are about a range s[i..j], and the answer for a range comes from shorter ranges inside it. The state is the pair (i, j), and the table is filled from short ranges to long ones — usually by running i from the end backwards, or by increasing length. Palindromes, Burst Balloons, Matrix Chain Multiplication and Stone Game are all interval DPs.
Let dp[i][j] be the answer inside s[i..j]. If the two end letters match, they can wrap whatever palindrome is best inside: dp[i][j] = 2 + dp[i+1][j-1]. If they differ, they can't both be used, so drop one: max(dp[i+1][j], dp[i][j-1]). One letter is a palindrome of length 1, and an empty range is 0.
function longestPalindromeSubseq(s) { const memo = new Map(); // "i,j" -> answer for s[i..j] const lps = (i, j) => { // longest palindromic subsequence inside s[i..j] if (i > j) return 0; // empty range if (i === j) return 1; // one letter const key = i + "," + j; if (memo.has(key)) return memo.get(key); const best = s[i] === s[j] ? 2 + lps(i + 1, j - 1) : Math.max(lps(i + 1, j), lps(i, j - 1)); memo.set(key, best); return best; }; return lps(0, s.length - 1);}Time O(n²), space O(n²). There are about n² / 2 ranges, each solved once. Without the memo it's O(2ⁿ): two mismatched ends branch both ways, and the same inner ranges get solved again and again.
Fill each row from the diagonal outwards: matching ends wrap the inside, otherwise drop one end.
function longestPalindromeSubseq(s) { const n = s.length; // dp[i][j]: the longest palindromic subsequence inside s[i..j] const dp = Array.from({ length: n }, () => new Array(n).fill(0)); for (let i = n - 1; i >= 0; i--) { // i goes down, so the row below is ready dp[i][i] = 1; // one letter is a palindrome for (let j = i + 1; j < n; j++) { if (s[i] === s[j]) dp[i][j] = dp[i + 1][j - 1] + 2; // both ends wrap the inside else dp[i][j] = Math.max(dp[i + 1][j], dp[i][j - 1]); // drop one end or the other } } return dp[0][n - 1];}Time O(n²), space O(n²). The fill order is the subtle part: dp[i][j] reads row i + 1 (below) and column j - 1 (left), so rows go bottom to top and each row left to right. When j = i + 1 and the letters match, dp[i+1][j-1] is a cell below the diagonal — an empty range, 0 — giving 2, as it should.
A palindrome reads the same backwards, so a palindromic subsequence of s is also a subsequence of reverse(s) — and the longest common one is the answer. That turns this into Longest Common Subsequence, with its two-row trick.
function longestPalindromeSubseq(s) { const t = [...s].reverse().join(""); // a palindrome is in both s and its reverse const n = s.length; let prev = new Array(n + 1).fill(0); for (let i = 1; i <= n; i++) { const cur = new Array(n + 1).fill(0); for (let j = 1; j <= n; j++) { cur[j] = s[i - 1] === t[j - 1] ? prev[j - 1] + 1 : Math.max(prev[j], cur[j - 1]); } prev = cur; // only the row above is needed } return prev[n]; // the LCS of s and its reverse}Time O(n²), space O(n). Reusing a known problem is a strong interview move — say why it's correct: any common subsequence of s and reverse(s) can be turned into a palindrome of the same length, and every palindromic subsequence is common to both.
"bbbab" gives 4 ("bbbb"), while the longest palindromic substring is "bbb", only 3.n - LPS.