Scale Engineer

Longest Palindromic Subsequence

Med
#0501Time: 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.3 companies
Patterns
Dynamic Programming
Data structures
String
Companies
CiscoLinkedInNutanix

Prompt

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 <= 1000
  • s consists 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 substring s[i...j].
  • Base Cases:
    • If i > j (empty substring), return 0.
    • If i == j (single character), return 1.
  • 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. Return 2 + 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)). Return max(solve(s, i + 1, j), solve(s, i, j - 1)).
  • 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:

  1. Base Cases:

    • If the start index i is greater than the end index j, it means we have an empty substring, so we return 0.
    • If i equals j, we have a single-character substring, which is always a palindrome of length 1.

  2. Recursive Step:

    • If the characters at the ends of the substring, s[i] and s[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 substring s[i+1...j-1]. So, we return 2 + solve(s, i + 1, j - 1).
    • If the characters s[i] and s[j] are different, we cannot include both in the same palindrome. We have two choices:
      • Exclude s[i] and find the LPS in s[i+1...j].
      • Exclude s[j] and find the LPS in s[i...j-1]. We take the maximum of these two possibilities: max(solve(s, i + 1, j), solve(s, i, j - 1)).

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.

Solutions

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 ]; } }

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.

← Previous

Previous problem

Next →

Next problem