Skills101
← All coding problems

Longest Palindromic Subsequence

mediumStrings II+20 XPTime limit 3s

A subsequence keeps some characters of a string in their original order, possibly skipping others (ace is a subsequence of abcde). Find the length of the longest subsequence that is a palindrome.

For bbbab the answer is 4 (bbbb). For skills it is 2 (ll or ss).

Input: one line with a string of lowercase letters.

Output: the length of the longest palindromic subsequence.

Constraints: 1 ≤ length ≤ 1000.

Think about it: interval DP. Let dp[i][j] be the answer for s[i..j]. If s[i] == s[j], they can wrap the best answer inside: dp[i+1][j−1] + 2. Otherwise drop one end: max(dp[i+1][j], dp[i][j−1]). Fill it for shorter intervals first — O(n²).

Sample input 1

bbbab

Sample output 1

4

Sample input 2

skills

Sample output 2

4

Read input from standard input and print the answer to standard output. Your code runs in a secure sandbox against the samples (Run) and hidden tests (Submit).

Loading editor…

Log in to run and submit your code — it's free.