Compute longest palindromic subsequence
J.P. MorganSoftware Engineer · Onsite
Last updated
This question evaluates understanding of dynamic programming for strings, specifically longest palindromic subsequence concepts such as memoization, bottom-up DP, space optimization and subsequence reconstruction.
Given a string s (1 ≤ |s| ≤ 2000), implement a function that returns the length of the longest subsequence of s that reads the same forward and backward. Provide both a top-down (memoized) and a bottom-up dynamic programming solution, analyze time and space complexity, and explain how to optimize space. Follow up: reconstruct one valid longest palindromic subsequence and discuss how to handle multiple test cases efficiently.
Solution walkthrough is for members
Get the full walkthrough with reference code and complexity analysis, plus Kitty Coach at 300 messages a day. Hints, the code runner and community answers stay free.