PPractick

The problem

You're building a "genetic symmetry detector" for a bioinformatics tool that scans DNA/RNA sequences for palindromic motifs (real biological structures — many restriction enzymes bind to palindromic DNA sequences). Characters don't need to be contiguous — you're looking for the longest subsequence of the given string s that reads the same forwards and backwards. Return the length of that longest palindromic subsequence (LPS).

Function signature

int longestPalindromeSubseq(string s);

Test cases

Input s	Output	Explanation
"bbbab"	4	"bbbb" is a palindromic subsequence of length 4
"cbbd"	2	"bb" is the longest palindromic subsequence
"a"	1	single character
""	0	empty string
"aaaa"	4	already fully a palindrome
"agbdba"	5	"abdba" or "agbga"-style — length 5 palindromic subsequence exists
"character"	5	e.g. "carac" is a palindromic subsequence of length 5

(Note: this asks for LENGTH only. A very common, closely related follow-up asks to return the actual subsequence string — be ready for that pivot.)

How interviewers phrase it

• "Given a string, find the length of the longest subsequence that is also a palindrome."
• "What's the longest palindrome you can form by deleting (not reordering) characters from this string?"
• Often given as a precursor to "Minimum Insertions to Make a String Palindrome" — if you've already solved that, recognize this is literally the core subroutine of it.

Clarifying questions to ask

1. Subsequence (order preserved, not contiguous) or substring (contiguous)? — Longest Palindromic Substring is a completely different, well-known problem (Manacher's / expand-around-center) — confirm explicitly which one is being asked.
2. Do you need just the length, or the actual subsequence string?
3. Are repeated characters counted normally (yes, by definition, since it's about symmetry, not distinct characters)?
4. Is the string guaranteed non-empty?
5. Expected input size — signals if O(n²) DP is acceptable (almost always yes for this problem).

Follow-ups to expect

1. "How does this relate to LCS?"
2. "Can you solve it with direct interval DP on s alone, without going through LCS?"
3. "Can you reconstruct the actual longest palindromic subsequence, not just its length?"
4. "Can you optimize space?"
5. "How is this different from 'Minimum Insertions to Make String Palindrome'?"
6. "What about Longest Palindromic SUBSTRING instead?"

Related questions

• Minimum insertions to make string palindrome Hard
• Longest common subsequence Hard
• Print Longest Common Subsequence Hard
• Longest common substring Hard
• Minimum insertions or deletions to convert string A to B Hard
• Shortest common supersequence Hard

All 474 dsa interview questions

DSA mock interviews · System design interview questions · Free mock interview practice · Browse interviewers · Sign in