LeetCode 516: Longest Palindromic Subsequence Solution in Python – A Step-by-Step Guide

What Is LeetCode 516: Longest Palindromic Subsequence?

In LeetCode 516: Longest Palindromic Subsequence, you’re given a string, and your task is to find the length of the longest subsequence (not necessarily contiguous) that forms a palindrome. A palindrome reads the same forward and backward, like “aba” or “racecar”. For example, in “bbbab”, the longest palindromic subsequence is “bbbb” (length 4). This problem builds on LeetCode 5: Longest Palindromic Substring, but focuses on subsequences rather than substrings.

Problem Statement

• Input: String s.
• Output: Integer—length of the longest palindromic subsequence.
• Rules: Subsequence can skip characters; must be palindromic.

Constraints

• 1 <= s.length <= 1000
• s contains only lowercase English letters.

Examples

• Input: "bbbab"
• Output: 4
• Subsequence: “bbbb” (b at 0, 1, 2, 4).
• Input: "cbbd"
• Output: 3
• Subsequence: “bbd” (or “cbb”).
• Input: "a"
• Output: 1
• Single char is a palindrome.

Understanding the Problem: Hunting Palindromic Subsequences

To solve LeetCode 516: Longest Palindromic Subsequence in Python, we need a method to find the longest sequence of characters in s that can be arranged into a palindrome, without requiring them to be consecutive. A naive approach might generate all subsequences and check for palindromes, but with up to 1000 characters, that’s impractical (2¹⁰⁰⁰ possibilities!). We’ll explore:

• Best Solution (DP with 2D Table): O(n²) time, O(n²) space—efficient and systematic.
• Alternative Solution (Recursive with Memoization): O(n²) time, O(n²) space—intuitive but recursive.

Let’s dive into the DP solution with a friendly breakdown!

Best Solution: Dynamic Programming with 2D Table

Why DP Wins

The DP with a 2D table is the best for LeetCode 516 because it efficiently computes the solution by breaking the problem into subproblems, using a table to store lengths of palindromic subsequences for all substring ranges. It runs in O(n²) time and O(n²) space, making it scalable for the constraints. It’s like building a map of palindrome possibilities, step by step!

How It Works

Think of this as a palindrome-building puzzle:

• Step 1: Define DP Table:
• dp[i][j]: Length of longest palindromic subsequence in s[i:j+1].
• Step 2: Base Case:
• Single char (i = j): dp[i][i] = 1.
• Step 3: Fill Table:
• If s[i] == s[j]: dp[i][j] = dp[i+1][j-1] + 2 (add both ends).
• Else: dp[i][j] = max(dp[i+1][j], dp[i][j-1]) (skip one end).
• Step 4: Return:
• dp[0][n-1]—full string’s longest palindromic subsequence.
• Why It Works:
• Builds from smaller to larger substrings.
• Captures all subsequence options.

It’s like a palindrome length calculator!

Step-by-Step Example

Example: "bbbab"

• Init: n = 5, dp = [[0]*5 for _ in range(5)].
• Base Case:
• dp[0][0] = 1 (b), dp[1][1] = 1 (b), etc.
• Fill Table (bottom-up, length 2 to 5):
• Length 2:
• i=0, j=1: “bb”, s[0]=s[1], dp[0][1] = dp[1][0] + 2 = 0 + 2 = 2.
• i=1, j=2: “bb”, dp[1][2] = 2.
• i=3, j=4: “ab”, s[3]≠s[4], dp[3][4] = max(dp[4][4], dp[3][3]) = 1.
• Length 3:
• i=0, j=2: “bbb”, dp[0][2] = dp[1][1] + 2 = 1 + 2 = 3.
• i=2, j=4: “bab”, dp[2][4] = dp[3][3] + 2 = 1 + 2 = 3.
• Length 5:
• i=0, j=4: “bbbab”, s[0]=s[4], dp[0][4] = dp[1][3] + 2 = 2 + 2 = 4.
• Result: dp[0][4] = 4.

Code with Detailed Line-by-Line Explanation

Here’s the Python code, explained for beginners:

class Solution:
    def longestPalindromeSubseq(self, s: str) -> int:
        n = len(s)

        # Step 1: Initialize DP table
        dp = [[0] * n for _ in range(n)]

        # Step 2: Base case - single characters
        for i in range(n):
            dp[i][i] = 1

        # Step 3: Fill DP table by substring length
        for length in range(2, n + 1):
            for i in range(n - length + 1):
                j = i + length - 1
                if s[i] == s[j] and length == 2:
                    dp[i][j] = 2
                elif 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])

        # Step 4: Return result for full string
        return dp[0][n - 1]

• Line 3: String length.
• Line 6: 2D table initialized with zeros.
• Lines 9-10: Single char palindromes = 1.
• Line 13: Loop over substring lengths.
• Lines 14-20: For each start i and end j:
• If ends match and length 2: 2.
• If ends match: Inner palindrome + 2.
• Else: Max of skipping left or right.
• Line 23: Full string’s result.
• Time Complexity: O(n²)—nested loops.
• Space Complexity: O(n²)—DP table.

It’s like a palindrome length builder!

Alternative Solution: Recursive with Memoization

Why an Alternative Approach?

The recursive solution with memoization computes the same result by breaking the string into subproblems, caching results to avoid recomputation. It’s O(n²) time and O(n²) space—intuitive for recursion fans but uses stack space. Great for learning memoization!

How It Works

Picture this as a recursive palindrome hunt:

• Step 1: Define recursive function:
• lps(i, j): Longest palindromic subsequence in s[i:j+1].
• Step 2: Memoize states (i, j).
• Step 3: Base case—single char or empty.
• Step 4: Recurrence—match or skip ends.

It’s like a memoized palindrome seeker!

Step-by-Step Example

Example: "cbbd"

• Init: memo = {}.
• Call: lps(0, 3):
• c≠d: max(lps(1,3), lps(0,2)).
• lps(1,3) (bbd): b=d, lps(2,2)+2 = 1+2 = 3.
• lps(0,2) (cbb): max(lps(1,2), lps(0,1)) = 2.
• Result: 3.
• Result: 3.

Code for Recursive Approach

class Solution:
    def longestPalindromeSubseq(self, s: str) -> int:
        n = len(s)
        memo = {}

        def lps(i, j):
            if i > j:  # Empty string
                return 0
            if i == j:  # Single char
                return 1
            if (i, j) in memo:
                return memo[(i, j)]

            if s[i] == s[j]:
                memo[(i, j)] = lps(i + 1, j - 1) + 2
            else:
                memo[(i, j)] = max(lps(i + 1, j), lps(i, j - 1))
            return memo[(i, j)]

        return lps(0, n - 1)

• Line 5: Memo cache.
• Lines 7-11: Base cases: empty or single char.
• Lines 14-17: Recurrence:
• Match: Inner + 2.
• No match: Max of skipping ends.
• Time Complexity: O(n²)—memoized states.
• Space Complexity: O(n²)—memo table.

It’s a recursive palindrome tracker!

Comparing the Two Solutions

• DP (Best):
• Pros: O(n²), clear bottom-up, efficient.
• Cons: Table setup.
• Recursive (Alternative):
• Pros: O(n²), intuitive.
• Cons: Stack overhead.

DP wins for clarity!

Additional Examples and Edge Cases

• ** "a": 1.
• ** "aaa": 3.
• ** "ab": 1.

DP handles them all!

Complexity Recap

• DP: Time O(n²), Space O(n²).
• Recursive: Time O(n²), Space O(n²).

DP’s the streamlined champ!

Key Takeaways

• DP: Table-based wins—learn at Python Basics!
• Memoization: Recursion with memory.
• Palindromes: Subsequence twist.
• Python: Arrays or dicts, your pick!

Final Thoughts: Find That Palindrome!

LeetCode 516: Longest Palindromic Subsequence in Python is a thrilling DP challenge. The 2D DP table is your fast path, while recursive memoization adds flair. Want more? Try LeetCode 5: Longest Palindromic Substring or LeetCode 647: Palindromic Substrings. Ready to hunt? Head to Solve LeetCode 516 on LeetCode and find that longest palindrome today!