Is Longest Palindromic Subsequence easy or hard?

The problem is classified as Medium because recognizing the DP state is the main challenge. Once you identify dp[i][j] for substring ranges and define the correct recurrence, the implementation becomes straightforward.

Longest Palindromic Subsequence Python/Java solution

Most implementations use a 2D DP array or memoization map. Python solutions typically use a list-of-lists DP table or functools.lru_cache for recursion, while Java solutions use a 2D int array and nested loops to fill substring ranges.

How to solve Longest Palindromic Subsequence in O(n^2)?

Use dynamic programming over substrings. Define dp[i][j] as the longest palindromic subsequence between indices i and j. If s[i] equals s[j], extend the inner result with 2 + dp[i+1][j-1]; otherwise take max(dp[i+1][j], dp[i][j-1]). Filling the table for all pairs yields an O(n^2) solution.

What is the best approach for Longest Palindromic Subsequence?

Dynamic programming is the standard approach. Build a DP table where dp[i][j] represents the longest palindromic subsequence in substring s[i..j]. By comparing characters at both ends and reusing previously computed results, the solution runs in O(n^2) time with O(n^2) space.

Is Longest Palindromic Subsequence asked at Google/Amazon/Meta?

Longest Palindromic Subsequence appears frequently in interviews at companies like Amazon, Google, and Meta because it tests dynamic programming fundamentals. Candidates must identify overlapping subproblems and design the correct DP state transition.

What data structure is used in Longest Palindromic Subsequence?

The primary data structure is a 2D dynamic programming table (matrix) that stores results for substring ranges. In top-down solutions, the same structure appears as a memoization cache keyed by index pairs.

What is the time complexity of Longest Palindromic Subsequence?

The optimal dynamic programming solution runs in O(n^2) time because every substring pair (i, j) is evaluated once. The DP table stores results for n^2 states, leading to O(n^2) space complexity as well.

Description Solution Video 9:38

516. Longest Palindromic Subsequence

Medium65.8% acceptance15 companies

Given a string s, find the longest palindromic subsequence's length in s.

A subsequence is a sequence that can be derived from another sequence by deleting some or no elements without changing the order of the remaining elements.

Example 1:

Input: s = "bbbab"
Output: 4
Explanation: One possible longest palindromic subsequence is "bbbb".

Example 2:

Input: s = "cbbd"
Output: 2
Explanation: One possible longest palindromic subsequence is "bb".

Constraints:

1 <= s.length <= 1000
s consists only of lowercase English letters.

Asked at 15 companies

Goldman Sachs Maq Software LinkedIn JPMorgan Chase Uber

TCS Nutanix Amazon Microsoft

Infosys Zoho Accenture

+3 more

Google Meta Bloomberg

Topics

Dynamic Programming String

9:38

Still stuck?Read 3 approaches, or watch a walkthrough.

Open solution

516. Longest Palindromic Subsequence

Asked at 15 companies

Topics

Similar problems