Longest Hidden Palindrome
Medium2-D Dynamic Programming
Problem
A string s may hide a palindrome among its characters: delete zero or more characters, keep the rest in order, and the result reads the same forwards and backwards.
Return the length of the longest such palindromic subsequence.
Example 1
- Input:
- s = "character"
- Output:
- 5
"carac" uses c, a, r, a, c in order.
Example 2
- Input:
- s = "abcd"
- Output:
- 1
No two characters are equal, so any single character is the best palindrome.
Constraints
- 1 ≤ s.length ≤ 1000
- s contains lowercase English letters only.
Hint
Show the first hint
Describe a sub-problem by the window s[i..j] it covers.
Walkthrough
How to approach it
01Clarify before coding
- Subsequence, not substring? Yes, the kept characters need not be adjacent.
- Is a single character a palindrome? Yes, so the answer is at least 1.
- Length only? Yes.
02Brute force
Generate every subsequence and keep the longest one that equals its reverse.
Cost: O(2^n · n): impossible for n = 1000.
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.
This problem is part of Pro.