Longest Palindromic Subsequence II solution and explanation
The problem
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 <= 250sconsists 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, thendfs(i, j, x) = 0; - If
s[i] = s[j]ands[i] neq x, thendfs(i, j, x) = dfs(i + 1, j - 1, s[i]) + 2; - If
s[i] neq s[j], thendfs(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.
class Solution:
def longestPalindromeSubseq(self, s: str) -> int:
@cache
def dfs(i, j, x):
if i >= j:
return 0
if s[i] == s[j] and s[i] != x:
return dfs(i + 1, j - 1, s[i]) + 2
return max(dfs(i + 1, j, x), dfs(i, j - 1, x))
ans = dfs(0, len(s) - 1, '')
dfs.cache_clear()
return ansclass Solution {
private int[][][] f;
private String s;
public int longestPalindromeSubseq(String s) {
int n = s.length();
this.s = s;
f = new int[n][n][27];
for (var a : f) {
for (var b : a) {
Arrays.fill(b, -1);
}
}
return dfs(0, n - 1, 26);
}
private int dfs(int i, int j, int x) {
if (i >= j) {
return 0;
}
if (f[i][j][x] != -1) {
return f[i][j][x];
}
int ans = 0;
if (s.charAt(i) == s.charAt(j) && s.charAt(i) - 'a' != x) {
ans = dfs(i + 1, j - 1, s.charAt(i) - 'a') + 2;
} else {
ans = Math.max(dfs(i + 1, j, x), dfs(i, j - 1, x));
}
f[i][j][x] = ans;
return ans;
}
}class Solution {
public:
int f[251][251][27];
int longestPalindromeSubseq(string s) {
int n = s.size();
memset(f, -1, sizeof f);
function<int(int, int, int)> dfs = [&](int i, int j, int x) -> int {
if (i >= j) return 0;
if (f[i][j][x] != -1) return f[i][j][x];
int ans = 0;
if (s[i] == s[j] && s[i] - 'a' != x)
ans = dfs(i + 1, j - 1, s[i] - 'a') + 2;
else
ans = max(dfs(i + 1, j, x), dfs(i, j - 1, x));
f[i][j][x] = ans;
return ans;
};
return dfs(0, n - 1, 26);
}
};func longestPalindromeSubseq(s string) int {
n := len(s)
f := make([][][]int, n)
for i := range f {
f[i] = make([][]int, n)
for j := range f[i] {
f[i][j] = make([]int, 27)
for k := range f[i][j] {
f[i][j][k] = -1
}
}
}
var dfs func(i, j, x int) int
dfs = func(i, j, x int) int {
if i >= j {
return 0
}
if f[i][j][x] != -1 {
return f[i][j][x]
}
ans := 0
if s[i] == s[j] && int(s[i]-'a') != x {
ans = dfs(i+1, j-1, int(s[i]-'a')) + 2
} else {
ans = max(dfs(i+1, j, x), dfs(i, j-1, x))
}
f[i][j][x] = ans
return ans
}
return dfs(0, n-1, 26)
}Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Subsequence Enumeration | O(2^n * n) | O(n) | Conceptual understanding of subsequences and constraints |
| Memoized DFS with Previous Character State | O(n^2 * 26) | O(n^2 * 26) | General solution expected in interviews |
| Bottom-Up 3D Dynamic Programming | O(n^2 * 26) | O(n^2 * 26) | When avoiding recursion or implementing iterative DP |
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.