Longest Palindromic Subsequence
MediumPractice library · +20 XPdynamic programmingstringlps
Given a string S, find the length of the longest palindromic subsequence. A subsequence is a sequence that can be derived from another sequence by deleting some or no elements without changing the order of the remaining elements. A palindrome is a sequence that reads the same backward as forward.
Input
A single line containing the string S.
Output
A single integer representing the length of the longest palindromic subsequence.
Constraints
1 <= |S| <= 1000. S consists of lowercase English letters.
Time limit 2 s (native code; slower languages get more)Memory 256 MB15 hidden tests
Example 1
Input
bbbab
Output
4
The longest palindromic subsequence is 'bbbb', which has length 4.
Example 2
Input
cbbd
Output
2
The longest palindromic subsequence is 'bb', which has length 2.
Hints
# Read the input from stdin and print the answer.
import sys
def main():
data = sys.stdin.read().split()
# your code here
main()
Example 1 input
bbbab
Example 2 input
cbbd