Longest Palindromic Subsequence

Problem Statement

Longest Palindromic Subsequence A palindrome is a sequence that reads the same forwards and backwards, such as tacocat or 12221 , but not 8675 . A subsequence is obtained by deleting zero or more characters from a sequence while keeping the order of the remaining characters. The subsequences of abc are a , b , c , ab , ac , bc and abc — note that ac is a subsequence even though a and c are not adjacent. You are given a string s of n lowercase English letters. Report the length of the longest palindromic subsequence of s . A single character is a palindrome, so the answer is always at least 1 . Input Format The first line contains one integer n , the length of s . The second line contains the string s . Output Format Print a single integer — the length of the longest palindromic subsequence of s . Constraints 1 <= n <= 5000 s consists of lowercase English letters 'a' – 'z' , and |s| = n Examples Example 1 Input: 2 ba Output: 1 Explanation: the only palindromic subsequences of ba a