Longest Palindromic Subsequence

Find the length of the longest palindromic subsequence in a given string.

strings dp subsequence palindrome dynamic-programming

A palindromic subsequence is a sequence of characters that can be obtained from the original string by deleting zero or more characters (preserving the relative order) and that reads the same forward and backward. Write a function `longest_palindromic_subsequence(s: str) -> int` that returns the length of the longest palindromic subsequence in the string `s`. If `s` is empty, return 0. The function must be efficient enough for strings of length up to 1000.

Constraints

- The input string `s` consists of printable ASCII characters.
- Length of `s` is between 0 and 1000 inclusive.
- The time complexity should be O(n^2), and the space complexity can be O(n) or O(n^2).

Example

```python
>>> longest_palindromic_subsequence("bbbab")
4
>>> longest_palindromic_subsequence("cbbd")
2
>>> longest_palindromic_subsequence("abc")
1
>>> longest_palindromic_subsequence("")
0
```

25 points ~30 min

Recent Submissions

No submissions yet — hit Run Tests to try!

Hints

Try to build the solution from smaller substrings: what is the answer for substrings of length 1 and 2?

If the first and last characters are equal, they can both be part of the palindrome. If not, you have to consider dropping one of them.

You can use a 2D DP table where dp[i][j] represents the answer for s[i:j+1]. Or you can optimize to O(n) space by using only the previous row.

Alternatively, the length of the longest palindromic subsequence is the length of the longest common subsequence between `s` and reversed `s`.

Test Results

Press Ctrl+Enter or click Run Tests to execute your code.