Microsoft Coding Interview: Longest Palindromic Subsequence

Problem overview

Given a string s, compute the length of its longest palindromic subsequence (LPS). A subsequence is formed by deleting zero or more characters without reordering. You should return an integer representing the maximum length of a subsequence of s that reads the same forwards and backwards. Handle edge cases such as the empty string and short inputs.

What you'll be asked to do

You will typically clarify constraints (n = |s|, allowed characters), discuss brute-force vs. DP, and then implement a correct solution. Interviewers expect you to explain time and space complexity, and optionally provide a space-optimized version. You may be asked to reconstruct the subsequence itself or adapt the approach for related problems.

High-level approach (flow)

1. Clarify input/output and examples.
2. Show a recursive relation: if s[i]==s[j], LPS(i,j)=2+LPS(i+1,j-1); else max of excluding one end.
3. Convert to bottom-up DP using a 2D table (or use LCS between s and reverse(s)).
4. Optimize space to O(n) by using rolling arrays when possible.
5. Test edge cases and analyze complexity.

Skill signals

You should demonstrate dynamic programming intuition, ability to derive recurrence relations, correctness reasoning, complexity analysis (O(n^2) time, O(n^2) or O(n) space), and familiarity with string-handling techniques (LCS reduction, two-pointer thinking, reconstruction).