Skip to main content
Talentd

Longest Palindromic Subsequence II - Solution & Explanation

MediumPremiumFree on FleetCodeStringDynamic Programming8 min read
Practice this problem

Problem Statement

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.

Approach Overview

Problem Overview: Given a string, return the length of the longest palindromic subsequence such that no two adjacent characters in the subsequence are the same. You can delete characters but must keep the relative order. The main challenge is enforcing both the palindrome structure and the adjacent-character constraint.

Approach 1: Brute Force Subsequence Enumeration (Exponential Time)

Generate every possible subsequence and check two conditions: whether the subsequence forms a palindrome and whether adjacent characters are different. Subsequence generation requires iterating through all 2^n combinations. Each candidate then needs a palindrome check and a linear scan to verify the adjacent constraint. This approach runs in O(2^n * n) time and O(n) space for recursion. It quickly becomes infeasible once the string length grows, but it helps clarify the problem constraints before introducing dynamic programming.

Approach 2: Memoized Search with Character State (Dynamic Programming) (O(n^2 * 26))

Use a top-down DP where the state is dfs(i, j, prev). The indices i and j define the current substring, and prev stores the character used in the outer palindrome layer. This extra state ensures the next chosen pair does not repeat the same character consecutively. If s[i] == s[j] and s[i] != prev, you can include both characters and recurse into dfs(i+1, j-1, s[i]). Otherwise, skip either side using dfs(i+1, j) or dfs(i, j-1). Memoizing results avoids recomputing overlapping subproblems.

The state space contains roughly n * n * 26 possibilities because the previous character can be one of the 26 lowercase letters (or none initially). Each state performs constant work, leading to O(n^2 * 26) time complexity and O(n^2 * 26) space for the memo table. This pattern is common in dynamic programming problems where additional constraints require expanding the DP state.

The key insight: standard longest palindromic subsequence DP only tracks substring boundaries. This problem adds a constraint about adjacent characters, so you must also track the previously chosen character. Combining substring DP with memoization keeps the search efficient while enforcing the rule.

This solution heavily relies on recursion with caching, a classic technique in dynamic programming and string problems involving subsequences.

Recommended for interviews: The memoized dynamic programming approach. Brute force demonstrates understanding of subsequences and palindrome validation, but the optimized DP shows you can identify overlapping subproblems and extend the state to enforce constraints. Interviewers expect the O(n^2 * alphabet) DP with memoization.

Solution

We design a function dfs(i, j, x) to represent the length of the longest "good" palindrome subsequence ending with character x in the index range [i, j] of string s. The answer is dfs(0, n - 1, 26).

The calculation process of the function dfs(i, j, x) is as follows:

  • If i >= j, then dfs(i, j, x) = 0;
  • If s[i] = s[j] and s[i] neq x, then dfs(i, j, x) = dfs(i + 1, j - 1, s[i]) + 2;
  • If s[i] neq s[j], then dfs(i, j, x) = max(dfs(i + 1, j, x), dfs(i, j - 1, x)).

During the process, we can use memorization search to avoid repeated calculations.

The time complexity is O(n^2 times C). Where n is the length of the string s, and C is the size of the character set. In this problem, C = 26.

Code

PythonJavaC++Go

Python

Java

C++

Go

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force Subsequence EnumerationO(2^n * n)O(n)Conceptual understanding of subsequences and constraints
Memoized DFS with Previous Character StateO(n^2 * 26)O(n^2 * 26)General solution expected in interviews
Bottom-Up 3D Dynamic ProgrammingO(n^2 * 26)O(n^2 * 26)When avoiding recursion or implementing iterative DP

Video Solution

Leetcode 1682. Longest Palindromic Subsequence II • Algorithms for Big Bucks • 383 views views

Watch 2 more video solutions →

Frequently Asked Questions

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.

Ready to solve this problem?

Practice Longest Palindromic Subsequence II with our built-in code editor and test cases.

Practice on FleetCode
Previous

Longest Palindromic Subsequence