🧞

Hmm...

Something unexpected happened with this submission. Let's see if Genie can help.

Longest Palindromic Subsequence

medium

Asked in Google Interview 2024 : SDE - I

Given a string S, find the length of the longest palindromic subsequence in S.

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.

Input Format:

The first and only line of input contains the string S consisting of only lowercase English alphabets. (1 ≤ |S| ≤ 1000)

Output Format:

Output a single integer representing the answer.

Constraints:

  • The string S consists only of lowercase English alphabets.
  • 1 ≤ |S| ≤ 1000

Examples:

Example 1:

Input:

bbbab

Output:

4

Example 2:

Input:

cbbd

Output:

2

Code

Loading Editor...