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).