423. The Longest Palindrome You Can Keep

Print the length of the longest SUBSEQUENCE of the string that reads the same forwards and backwards. A subsequence keeps the original order but may delete any characters.

bbbab -> 4 bbbb character -> 5 carac

The state is the surprise. A single index is not enough, because deciding whether to keep a character requires knowing what is still available at BOTH ends. So the state is a RANGE:

best(i, j) = the longest palindromic subsequence of s[i..j]

and the recursion compares the two ends:

i > j -> 0 empty range i == j -> 1 single character s[i] == s[j] -> best(i+1, j-1) + 2 otherwise -> max( best(i+1, j), best(i, j-1) )

When the ends match, taking both is always at least as good as taking either alone, so there is no branch to consider there.

Bottom-up, the order must fill SHORT ranges before long ones, since every sub-range is strictly shorter. Iterating i downwards and j upwards from i achieves that, and getting the direction wrong reads uninitialised entries.

There is a one-line alternative: this equals the longest common subsequence of the string and its reverse. That is a correct reduction to problem #237 and worth knowing, though the range recursion is what generalises.

Constraints - `1 ≤ length ≤ 1000` - The string is lowercase English letters.