Longest Palindromic Subsequence
MediumAsked in:Amazon•Stage:Onsite
stringdynamic_programming
Problem Statement
Given a string s, find the length of the longest subsequence of s that reads the same forward and backward. A subsequence is obtained by deleting zero or more characters without changing the order of the remaining characters. The solution should run efficiently for the given constraints.
Input Format
A single line containing the string s consisting of lowercase and/or uppercase English letters. Let n be the length of s.
Output Format
Print a single integer representing the length of the longest palindromic subsequence of s.
Constraints
- 1 <= n <= 10^5
- s contains only English letters