Skip to main content
Back to problems
Leetcode
Medium
Dynamic Programming
DP on Strings
Strings
Google
Meta
Longest Palindromic Subsequence

Find the length of the longest subsequence of a string that reads the same forward and backward.

Acceptance 100%
Start Practice
Problem Statement

Given a string s, determine the length of the longest palindromic subsequence in s.

A subsequence is formed by deleting zero or more characters without changing the order of the remaining characters. The subsequence does not need to be contiguous.

Return only the maximum possible length.

Input Format

  • A single string s.
  • You may assume s contains lowercase English letters unless stated otherwise by the platform.

Output Format

  • Return one integer: the length of the longest palindromic subsequence in s.

Constraints

  • 1≤∣s∣1 \le |s|
  • The intended solution is typically O(n2)O(n^2) time with O(n2)O(n^2) or optimized O(n)O(n) additional space.
  • Exact platform constraints are not provided here; use the standard LeetCode formulation.
Examples
Sample cases returned by the problem API.

Example 1

Input

s = "bbbab"

Output

4

Explanation

One longest palindromic subsequence is "bbbb".

Example 2

Input

s = "cbbd"

Output

2

Explanation

One longest palindromic subsequence is "bb".

Premium problem context

Unlock deeper context for this problem

Premium adds guided hints, editorial links, similar variants, discussion resources, and concept maps so you can understand why a problem matters, not just solve it once.

Guided hints
Editorial and discussion links
Concept map and variants
Sign in to unlock
Track your progress
Sign in to bookmark this problem, save notes, and manage its revision plan.
Sign in to track progress