### 516. Longest Palindromic Subsequence

Given a string s, find the longest palindromic subsequence's length in s. You may assume that the maximum length of s is 1000.

Example 1:
Input:

"bbbab"

Output:
4

One possible longest palindromic subsequence is "bbbb".

Example 2:
Input:

"cbbd"

Output:
2

One possible longest palindromic subsequence is "bb".

Seen this question in a real interview before?
When did you encounter this question?
Which stage?
Which company?