Free Timed practice lessonsTimed practice · Stage 0 · Timed set 1 · Step 2

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?

Look at both ends: of a stretch, then shrink it.

Longest palindrome inside each stretch of b b a b · row is the start, column is the end

end bend bend aend b

start b

start a

start b

A stretch of one letter is a palindrome of length 1.

Move 1 of 4

Quick check

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?

Show the answer

3. Keep both ends and the best inside: 2 + 1 = 3.

Your problem

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.

Example

s = "bbab" → 3

1 ≤ length ≤ 1,000 · lowercase letters

Solve it in your browserFree account, no card. Python, C++, Java or JavaScript, with hints if you get stuck, and your progress is saved.