Longest Palindromic Subsequence
MedPrompt
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 <= 1000sconsists only of lowercase English letters.
Approaches
3 approaches with complexity analysis and trade-offs.
This approach solves the problem by breaking it down into smaller, overlapping subproblems using recursion. We define a function that calculates the length of the longest palindromic subsequence for a given substring. The solution explores all possibilities without storing intermediate results, leading to exponential time complexity.
Algorithm
- Define a recursive function
solve(s, i, j)that computes the length of the longest palindromic subsequence in the substrings[i...j]. - Base Cases:
- If
i > j(empty substring), return 0. - If
i == j(single character), return 1.
- If
- Recursive Step:
- If
s.charAt(i) == s.charAt(j), the characters at the ends match. They contribute 2 to the length. The rest of the palindrome is found in the inner substring. Return2 + solve(s, i + 1, j - 1). - If
s.charAt(i) != s.charAt(j), the end characters don't match. We must discard one of them. We find the maximum length by either excluding the start character (solve(s, i + 1, j)) or the end character (solve(s, i, j - 1)). Returnmax(solve(s, i + 1, j), solve(s, i, j - 1)).
- If
- The initial call is
solve(s, 0, s.length() - 1).
Walkthrough
We define a recursive function, say solve(s, i, j), which computes the length of the longest palindromic subsequence in the substring s[i...j]. The logic is as follows:
-
Base Cases:
- If the start index
iis greater than the end indexj, it means we have an empty substring, so we return 0. - If
iequalsj, we have a single-character substring, which is always a palindrome of length 1.
- If the start index
-
Recursive Step:
- If the characters at the ends of the substring,
s[i]ands[j], are the same, they can form the ends of a palindrome. The length will be 2 plus the length of the LPS in the inner substrings[i+1...j-1]. So, we return2 + solve(s, i + 1, j - 1). - If the characters
s[i]ands[j]are different, we cannot include both in the same palindrome. We have two choices:- Exclude
s[i]and find the LPS ins[i+1...j]. - Exclude
s[j]and find the LPS ins[i...j-1]. We take the maximum of these two possibilities:max(solve(s, i + 1, j), solve(s, i, j - 1)).
- Exclude
- If the characters at the ends of the substring,
The initial call to find the answer for the whole string s would be solve(s, 0, s.length() - 1). This method recomputes the same subproblems multiple times, making it highly inefficient.
class Solution { public int longestPalindromeSubseq(String s) { return solve(s, 0, s.length() - 1); } private int solve(String s, int i, int j) { // Base case 1: Empty substring if (i > j) { return 0; } // Base case 2: Single character substring if (i == j) { return 1; } // If characters at both ends match if (s.charAt(i) == s.charAt(j)) { return 2 + solve(s, i + 1, j - 1); } else { // If characters do not match return Math.max(solve(s, i + 1, j), solve(s, i, j - 1)); } }}Complexity
Time
O(2^n), where n is the length of the string. For each position where characters don't match, the function branches into two subproblems, leading to an exponential number of calls.
Space
O(n), where n is the length of the string. This space is used by the recursion stack. In the worst-case scenario, the recursion depth can go up to n.
Trade-offs
Pros
Simple to understand and implement.
Directly follows the problem's recursive definition.
Cons
Extremely inefficient due to a large number of redundant computations for the same subproblems.
Will result in a 'Time Limit Exceeded' (TLE) error on most platforms for non-trivial input sizes.
This approach is an optimization of the brute-force recursion. It uses a 2D array (or a hash map) to store the results of subproblems that have already been solved. This technique, known as memoization, avoids redundant calculations and drastically improves the time complexity from exponential to polynomial.
Algorithm
- Create a 2D array
memo[n][n]to store the results of subproblems, initialized with a sentinel value (e.g.,nullor-1). - Define a recursive function
solve(s, i, j, memo). - Base Cases: Same as the brute-force approach.
- Memoization Check: Before computing, check if
memo[i][j]has already been computed. If so, return the stored value. - Recursive Step: Same logic as the brute-force approach.
- Store Result: After computing the result for
(i, j), store it inmemo[i][j]before returning.
Walkthrough
The recursive structure remains the same as the brute-force approach. The key difference is the addition of a memoization table, memo, typically a 2D array initialized with a sentinel value (like null or -1) to indicate that a subproblem's result has not been computed yet.
The function solve(s, i, j, memo) works as follows:
- Before any computation, it checks if
memo[i][j]already contains a valid result. If so, it returns the stored value immediately. - If not, it computes the result using the same recursive logic as before.
- Before returning the computed result, it stores it in
memo[i][j]for future use.
This ensures that each subproblem (i, j) is solved only once.
class Solution { public int longestPalindromeSubseq(String s) { int n = s.length(); Integer[][] memo = new Integer[n][n]; return solve(s, 0, n - 1, memo); } private int solve(String s, int i, int j, Integer[][] memo) { if (i > j) { return 0; } if (i == j) { return 1; } if (memo[i][j] != null) { return memo[i][j]; } int result; if (s.charAt(i) == s.charAt(j)) { result = 2 + solve(s, i + 1, j - 1, memo); } else { result = Math.max(solve(s, i + 1, j, memo), solve(s, i, j - 1, memo)); } memo[i][j] = result; return result; }}Complexity
Time
O(n^2). There are n*n possible unique subproblems defined by the pair `(i, j)`. Each subproblem is solved only once due to memoization.
Space
O(n^2), for the memoization table. The recursion stack also uses O(n) space, so the total space is dominated by the table.
Trade-offs
Pros
Significantly more efficient than brute-force, with a polynomial time complexity.
Guaranteed to pass within time limits for the given constraints.
The code structure is still intuitive and closely follows the recursive definition.
Cons
Uses O(n^2) space, which might be substantial for very large n.
Recursive solutions can lead to stack overflow errors for very deep recursion, although this is unlikely given the problem constraints (n <= 1000).
This approach iteratively builds the solution from the smallest subproblems to the largest, eliminating recursion. It first solves for all substrings of length 1, then length 2, and so on, until it solves for the entire string. This bottom-up approach can be further optimized in terms of space from O(n^2) to O(n).
Algorithm
- Create a 1D array
dpof sizen. - Iterate from the end of the string to the beginning with index
i(fromn-1down to0). This represents the starting character of the substring. - For each
i, setdp[i] = 1(a single character is a palindrome of length 1). - Initialize a
prevvariable to 0. This will hold the value ofdp[i+1][j-1]needed for the calculation. - Start an inner loop for
jfromi+1ton-1. This represents the ending character of the substring. - Inside the inner loop, save
dp[j](which currently holdsdp[i+1][j]) into atempvariable. - If
s.charAt(i) == s.charAt(j), updatedp[j] = 2 + prev. - Otherwise, update
dp[j] = max(dp[j], dp[j-1]). - After the update, set
prev = tempto prepare for the nextjiteration. - After the loops complete,
dp[n-1]will hold the result for the entire strings[0...n-1].
Walkthrough
Instead of a top-down recursive approach, we can solve the problem iteratively, or bottom-up. We can use a 2D DP table, dp[n][n], where dp[i][j] stores the length of the longest palindromic subsequence in s[i...j]. We would fill this table for substrings of increasing length.
The recurrence relation is the same:
- If
s[i] == s[j],dp[i][j] = 2 + dp[i+1][j-1]. - If
s[i] != s[j],dp[i][j] = max(dp[i+1][j], dp[i][j-1].
Space Optimization
Observing the recurrence, we see that to compute the i-th row of the DP table, we only need information from the (i+1)-th row. This allows us to optimize the space from O(n^2) to O(n) by using only one 1D array.
We iterate i from n-1 down to 0. A 1D array dp of size n will represent the current row being computed. At each step j in the inner loop, dp[j] still holds the value from the previous row (i+1), while dp[j-1] has already been updated for the current row i. A prev variable is used to keep track of the diagonal element dp[i+1][j-1].
class Solution { public int longestPalindromeSubseq(String s) { int n = s.length(); int[] dp = new int[n]; for (int i = n - 1; i >= 0; i--) { dp[i] = 1; // Base case for substring of length 1 int prev = 0; // Stores dp[i+1][j-1] for (int j = i + 1; j < n; j++) { int temp = dp[j]; // Store dp[i+1][j] before it's overwritten if (s.charAt(i) == s.charAt(j)) { dp[j] = 2 + prev; } else { dp[j] = Math.max(dp[j], dp[j-1]); } prev = temp; } } return dp[n - 1]; }}Complexity
Time
O(n^2). We have two nested loops, each iterating up to `n` times, to fill the DP states.
Space
O(n). We use a single 1D array of size `n` to store the necessary DP states, making this the most memory-efficient approach.
Trade-offs
Pros
Most efficient approach in terms of both time and space.
Iterative solution avoids recursion overhead and any risk of stack overflow.
Cons
The logic, especially with the single-array space optimization, can be less intuitive to understand compared to the more direct recursive or 2D DP solutions.
Solutions
Solution
class Solution { public int longestPalindromeSubseq ( String s ) { int n = s . length (); int [][] dp = new int [ n ][ n ]; for ( int i = 0 ; i < n ; ++ i ) { dp [ i ][ i ] = 1 ; } for ( int j = 1 ; j < n ; ++ j ) { for ( int i = j - 1 ; i >= 0 ; -- i ) { if ( s . charAt ( i ) == s . charAt ( j )) { dp [ i ][ j ] = dp [ i + 1 ][ j - 1 ] + 2 ; } else { dp [ i ][ j ] = Math . max ( dp [ i + 1 ][ j ], dp [ i ][ j - 1 ]); } } } return dp [ 0 ][ n - 1 ]; } }class Solution { public: int longestPalindromeSubseq ( string s ) { int n = s . size (); vector < vector < int >> dp ( n , vector < int > ( n , 0 )); for ( int i = 0 ; i < n ; ++ i ) { dp [ i ][ i ] = 1 ; } for ( int j = 1 ; j < n ; ++ j ) { for ( int i = j - 1 ; i >= 0 ; -- i ) { if ( s [ i ] == s [ j ]) { dp [ i ][ j ] = dp [ i + 1 ][ j - 1 ] + 2 ; } else { dp [ i ][ j ] = max ( dp [ i + 1 ][ j ], dp [ i ][ j - 1 ]); } } } return dp [ 0 ][ n - 1 ]; } };class Solution : def longestPalindromeSubseq ( self , s : str ) -> int : n = len ( s ) dp = [[ 0 ] * n for _ in range ( n )] for i in range ( n - 1 , - 1 , - 1 ): dp [ i ][ i ] = 1 # pre-set before inner loop for j in range ( i + 1 , n ): if s [ i ] == s [ j ]: dp [ i ][ j ] = dp [ i + 1 ][ j - 1 ] + 2 else : dp [ i ][ j ] = max ( dp [ i + 1 ][ j ], dp [ i ][ j - 1 ]) return dp [ 0 ][ - 1 ] ########### class Solution : def longestPalindromeSubseq ( self , s : str ) -> int : n = len ( s ) dp = [[ 0 ] * n for _ in range ( n )] for i in range ( n ): dp [ i ][ i ] = 1 # cannot move it inside 'for j in range(1, n)' # because below 'for j in range' starting at 1 # so cannot put dp[j][j]=1 inside below for loop for j in range ( 1 , n ): for i in range ( j - 1 , - 1 , - 1 ): if s [ i ] == s [ j ]: dp [ i ][ j ] = dp [ i + 1 ][ j - 1 ] + 2 # "aa" => i=0,j=1 => dp[1][0] is 0, still works else : dp [ i ][ j ] = max ( dp [ i + 1 ][ j ], dp [ i ][ j - 1 ]) return dp [ 0 ][ - 1 ]Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.