How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a medium difficulty Coding & Algorithms question, commonly asked during Onsite rounds at J.P. Morgan.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at J.P. Morgan during technical interviews.

Compute longest palindromic subsequence | J.P. Morgan Coding Question

Compute longest palindromic subsequence

Company: J.P. Morgan

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Onsite

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.

Quick Answer: 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.

Part 1: Compute the Length of the Longest Palindromic Subsequence

Given a string s, return the length of its longest palindromic subsequence. A subsequence is formed by deleting zero or more characters without changing the order of the remaining characters. The subsequence does not need to be contiguous.

Constraints

0 <= len(s) <= 2000
Character comparisons are case-sensitive.

Examples

Input: "bbbab"

Expected Output: 4

Explanation: One longest palindromic subsequence is 'bbbb'.

Input: "cbbd"

Expected Output: 2

Explanation: The longest palindromic subsequence is 'bb'.

Hints

Try defining dp[i][j] as the answer for the substring from index i to j.
If s[i] == s[j], those two characters can wrap a smaller palindromic subsequence. Otherwise, try skipping one end.

Part 2: Reconstruct One Longest Palindromic Subsequence

Given a string s, return one longest palindromic subsequence of s. If multiple longest palindromic subsequences exist, use this deterministic tie-break rule while reconstructing from the DP table: when skipping the left character and skipping the right character both keep the optimal length, skip the left character first. This makes the expected output unique.

Constraints

0 <= len(s) <= 2000
The returned value must be both a palindrome and a subsequence of s.
Character comparisons are case-sensitive.

Examples

Input: "bbbab"

Expected Output: "bbbb"

Explanation: The reconstruction picks matching outer b characters and then another matching pair.

Input: "cbbd"

Expected Output: "bb"

Explanation: The longest palindromic subsequence is uniquely 'bb'.

Hints

First compute the LPS length for every substring, then walk inward from both ends to rebuild an answer.
Build the result using a left half and a right half; when both skip choices are equally good, move the left pointer forward.

Quick Overview

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.