Longest mirror subsequence
The longest palindrome you can make by deleting letters from a word. About 14 minutes.
Which two ends are you comparing?
A palindrome reads the same forwards and backwards, so its first and last letters match. Look at the first and last letters of any stretch of the word. If they match, both can be kept, around whatever is best inside. If they don't, one of them has to go.
So ask: what smaller stretches do I need an answer for, and in what order can I fill them in?
A stretch of one letter is a palindrome of length 1.
In the word b b a b, the first and last letters match. The best palindrome inside the middle, b a, has length 1. What is the best palindrome for the whole word?
- A3
- B2
- C4
Show the answer
3. Keep both ends and the best inside: 2 + 1 = 3.
Longest mirror subsequence
Given a string s, return the length of the longest palindromic subsequence: the longest sequence of letters that reads the same forwards and backwards and can be made by deleting zero or more letters without reordering the rest.
s = "bbab" → 3
1 ≤ length ≤ 1,000 · lowercase letters