Compute longest palindromic subsequence
Company: J.P. Morgan
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: Medium
Interview Round: Onsite
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
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'.
Input: "agbdba"
Expected Output: 5
Explanation: One longest palindromic subsequence is 'abdba'.
Input: "a"
Expected Output: 1
Explanation: A single character is always a palindrome of length 1.
Input: ""
Expected Output: 0
Explanation: The empty string has no subsequences, so the answer is 0.
Solution
def solution(s):
if not s:
return 0
n = len(s)
dp = [0] * n
for i in range(n - 1, -1, -1):
dp[i] = 1
prev = 0
for j in range(i + 1, n):
temp = dp[j]
if s[i] == s[j]:
dp[j] = prev + 2
else:
dp[j] = max(dp[j], dp[j - 1])
prev = temp
return dp[-1]Time complexity: O(n^2). Space complexity: O(n).
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
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'.
Input: "agbdba"
Expected Output: "abdba"
Explanation: A full optimal reconstruction is 'abdba'.
Input: "abcda"
Expected Output: "ada"
Explanation: Several length-3 answers exist, and the required tie-break rule leads to 'ada'.
Input: ""
Expected Output: ""
Explanation: The empty string reconstructs to the empty palindrome.
Solution
def solution(s):
if not s:
return ''
from array import array
n = len(s)
dp = [array('H', [0]) * n for _ in range(n)]
for i in range(n - 1, -1, -1):
dp[i][i] = 1
for j in range(i + 1, n):
if s[i] == s[j]:
dp[i][j] = dp[i + 1][j - 1] + 2
else:
dp[i][j] = max(dp[i + 1][j], dp[i][j - 1])
left = []
right = []
i, j = 0, n - 1
while i <= j:
if i == j:
left.append(s[i])
break
if s[i] == s[j] and dp[i][j] == dp[i + 1][j - 1] + 2:
left.append(s[i])
right.append(s[j])
i += 1
j -= 1
elif dp[i + 1][j] >= dp[i][j - 1]:
i += 1
else:
j -= 1
return ''.join(left + right[::-1])Time complexity: O(n^2). Space complexity: O(n^2).
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.