How do you solve Longest Palindromic Subsequence on LeetCode?

Longest Palindromic Subsequence (LeetCode #516) can be solved using Brute Force or Optimal Solution. The optimal approach is Optimal Solution with O(n²) time complexity and O(n²) space complexity. Key insight: A palindromic subsequence can be formed by characters that are the same and are symmetrically positioned.

What is the brute force solution for Longest Palindromic Subsequence?

The brute force approach for Longest Palindromic Subsequence is Brute Force, with O(2^n) time complexity and O(n) space complexity. The brute-force approach generates all possible subsequences of the string and checks which ones are palindromic. This is straightforward but inefficient due to the exponential number of subsequences. The optimal Optimal Solution approach improves this to O(n²).

What algorithm or data structure is used to solve Longest Palindromic Subsequence?

Longest Palindromic Subsequence uses the following concepts: String, Dynamic Programming. The recommended patterns to study are: Dynamic Programming, Two Pointers.

What are the interview tips for Longest Palindromic Subsequence?

Explain your thought process clearly while coding. Discuss edge cases, such as strings with all identical characters. Practice writing dynamic programming solutions to become familiar with the approach.

What are common mistakes when solving Longest Palindromic Subsequence?

Not considering all characters when checking for palindromes. Failing to initialize the DP table correctly.

#516

Longest Palindromic Subsequence

Medium

StringDynamic ProgrammingDynamic ProgrammingTwo Pointers

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution★
Time	O(2^n)	O(n²)
Space	O(n)	O(n²)

💡

Intuition

Time O(n²)Space O(n²)

The optimal approach uses dynamic programming to build a table that stores the lengths of palindromic subsequences. This avoids redundant calculations and reduces the time complexity significantly.

⚙️

Algorithm

3 steps

1Step 1: Create a 2D array dp where dp[i][j] will store the length of the longest palindromic subsequence in s[i:j+1].
2Step 2: Initialize the table: all single characters are palindromes of length 1.
3Step 3: Fill the table by checking pairs of characters and building on previously computed values.

solution.py20 lines

1# Full working Python code
2
3def longest_palindromic_subsequence(s):
4    n = len(s)
5    dp = [[0] * n for _ in range(n)]
6
7    for i in range(n):
8        dp[i][i] = 1  # Each character is a palindrome of length 1
9
10    for length in range(2, n + 1):
11        for i in range(n - length + 1):
12            j = i + length - 1
13            if s[i] == s[j]:
14                dp[i][j] = dp[i + 1][j - 1] + 2
15            else:
16                dp[i][j] = max(dp[i + 1][j], dp[i][j - 1])
17
18    return dp[0][n - 1]
19
20print(longest_palindromic_subsequence('bbbab'))  # Output: 4

ℹ

Complexity note: The time complexity is O(n²) because we fill a 2D table of size n x n. The space complexity is also O(n²) for storing the lengths of palindromic subsequences.

1A palindromic subsequence can be formed by characters that are the same and are symmetrically positioned.
2Dynamic programming helps in breaking down the problem into smaller overlapping subproblems.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.