Where it runs
1. The problem
The DP lessons so far filled a table in a plain sweep. The one-dimensional table (step 111) grew from left to right. The grid (step 113) was filled row by row. Knapsack (step 114) and the longest increasing subsequence (step 115) read only cells that this sweep had already written earlier. So the usual order "row by row, left to right" was always enough. In this lesson a cell depends on a shorter piece inside itself, and the fill order has to change.
Here is the problem. A subsequence is what is left after you delete some letters without moving the rest: "ace" is a subsequence of "abcde". A palindrome reads the same forwards and backwards. longestPalindromeSubseq(s) returns the length of the longest subsequence of s that is a palindrome. For "bbbab" the answer is 4 ("bbbb"). For "cbbd" it is 2 ("bb"). For "abcde" it is 1, because no letter repeats.
This step is part of the paid track
The first 33 steps are open to everyone: lesson, exercise and tests. This one opens with full access. Start with a free account and the free steps.
Create a free accountSee what is includedOn LeetCode
Palindrome problems on substrings and subsequences. The cell for i to j comes from shorter ranges inside it, so fill the table by range length, from 2 up to n.
The lesson task, word for word.
Mark cell i to j true when the end letters match and the inside is a palindrome, then count the true cells.
The same true or false table, keeping the longest true range. n is at most 1000, so n^2 cells pass.
Every letter outside the longest palindromic subsequence needs a partner, so the answer is n minus the lesson's result.