Longest Palindromic Subsequence II - Solution & Explanation

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.