Solvarch
DSA ProblemsProgressPlanRoadmapsReviewCheat SheetsCompaniesSystem DesignCS FundamentalsQuestion Bank
Theme
Problems

Longest Palindromic Subsequence

Medium
dynamic-programmingstringinterval-dp

Return the length of the longest subsequence of s that is a palindrome. A subsequence keeps relative order but need not be contiguous.

Input: one line, the string s. Output: the length of the longest palindromic subsequence.

Example 1
Input:
bbbab
Output:
4

"bbbb".

Example 2
Input:
cbbd
Output:
2

"bb".

Example 3
Input:
agbdba
Output:
5

"abdba".

Constraints

  • 1 ≤ s.length ≤ 1000
  • Lowercase English letters.
Watch a video walkthrough

Run your code against the sample tests, or Submit to run the full suite.