algoadvance

Leetcode 516. Longest Palindromic Subsequence

Problem Statement

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

Clarifying Questions

  1. Input Constraints:
    • What are the constraints on the string length (n)?
      • (Typically, this will be something manageable, e.g., ( 1 \leq n \leq 1000 ))
    • Can the string contain special characters, or is it limited to lowercase/uppercase letters?
    • (Assume it contains only lowercase English letters for simplicity here.)
  2. Output:
    • Should we return the length of the subsequence, or the subsequence itself?
    • (We need to return the length of the longest palindromic subsequence.)
  3. Edge Cases:
    • What if the string is empty?
    • (Assume the length will be zero in this case.)
    • What if the string length is 1?
    • (A single character is a palindrome of length 1.)

Strategy

We need to find the longest palindromic subsequence. This can be achieved using dynamic programming. Here’s the approach:

  1. Define a DP Table: Let dp[i][j] represent the length of the longest palindromic subsequence within the substring s[i:j+1].

  2. Base Cases:
    • If i == j, the length is 1 because a single character is a palindrome.
    • If i > j, this doesn’t make sense in our context since it represents an invalid range.
  3. Recurrence Relation:
    • If s[i] == s[j], then dp[i][j] = 2 + dp[i+1][j-1].
    • If s[i] != s[j], then dp[i][j] = max(dp[i+1][j], dp[i][j-1]).
  4. Filling the Table:
    • We will fill this table diagonally (from the base case upwards).
  5. Extract Result:
    • The result will be in dp[0][n-1] which includes the entire string.

Code Implementation

#include <vector>
#include <string>
#include <algorithm>

using namespace std;

int longestPalindromeSubseq(string s) {
    int n = s.size();
    if (n == 0) return 0;
    vector<vector<int>> dp(n, vector<int>(n, 0));
    
    // Base cases: A single character is a palindrome of length 1
    for (int i = 0; i < n; ++i) {
        dp[i][i] = 1;
    }
    
    // Fill the table
    for (int len = 2; len <= n; ++len) { // starting from length 2 to n
        for (int i = 0; i <= n - len; ++i) {
            int j = i + len - 1;
            if (s[i] == s[j]) {
                dp[i][j] = 2 + dp[i+1][j-1];
            } else {
                dp[i][j] = max(dp[i+1][j], dp[i][j-1]);
            }
        }
    }
    
    // The result is in dp[0][n-1]
    return dp[0][n-1];
}

Time Complexity

This solution is optimal for the constraints typically provided in competitive programming and interviews.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI