Is Longest Palindromic Subsequence II easy or hard?

Longest Palindromic Subsequence II is typically rated Medium because the base palindrome subsequence problem is well known. The difficulty comes from adding the adjacent-character restriction, which requires extending the DP state with the previously used character.

Longest Palindromic Subsequence II Python/Java solution

Most implementations use a recursive DFS with memoization. The function tracks the substring boundaries and the previous character, storing results in a dictionary or 3D DP array. The same logic works across Python, Java, C++, and Go with identical O(n^2 * 26) complexity.

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

An O(n) solution is not known for this problem because the palindrome subsequence decision depends on pairs of indices across the string. Dynamic programming must consider O(n^2) substring ranges, and the extra character constraint introduces another factor based on the alphabet size.

What is the best approach for Longest Palindromic Subsequence II?

The most effective approach uses memoized dynamic programming with a state (i, j, prevChar). The indices define the current substring and prevChar tracks the last chosen outer character to enforce the adjacent-character constraint. This reduces the search space to O(n^2 * 26) states while guaranteeing valid palindromes.

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

Variants of longest palindromic subsequence and constrained DP problems frequently appear in interviews at companies like Google, Amazon, and Meta. The pattern of adding extra state to enforce constraints is a common dynamic programming interview theme.

What data structure is used in Longest Palindromic Subsequence II?

The solution primarily uses dynamic programming with a memoization table or cache keyed by (i, j, prevChar). Recursion or iterative DP manages substring states while the memo structure avoids recomputation.

What is the time complexity of Longest Palindromic Subsequence II?

The optimized memoized DP runs in O(n^2 * 26) time. There are O(n^2) substring states and up to 26 possibilities for the previously chosen character. Each state performs constant work after memoization.

Description Hints 2 Solution Video 9:49

1682. Longest Palindromic Subsequence II

Medium50.1% acceptancePremium elsewhere, free here

A subsequence of a string s is considered a good palindromic subsequence if:

It is a subsequence of s.
It is a palindrome (has the same value if reversed).
It has an even length.
No two consecutive characters are equal, except the two middle ones.

For example, if s = "abcabcabb", then "abba" is considered a good palindromic subsequence, while "bcb" (not even length) and "bbbb" (has equal consecutive characters) are not.

Given a string s, return the length of the longest good palindromic subsequence in s.

Example 1:

Input: s = "bbabab"
Output: 4
Explanation: The longest good palindromic subsequence of s is "baab".

Example 2:

Input: s = "dcbccacdb"
Output: 4
Explanation: The longest good palindromic subsequence of s is "dccd".

Constraints:

1 <= s.length <= 250
s consists of lowercase English letters.

Topics

Dynamic Programming String

Hints open one at a time

Hint 1

As with any good dp problem that uses palindromes, try building the palindrome from the edges

Hint 2

The prime point is to check that no two adjacent characters are equal, so save the past character while building the palindrome.

9:49

Still stuck?Read the written solution, or watch a walkthrough.

Open solution

1682. Longest Palindromic Subsequence II

Topics

Hints open one at a time

Similar problems