Good morning! Here's your coding interview problem for today.
This problem was asked by Google.
Given a string, return the length of the longest palindromic subsequence in the string.
For example, given the following string:
MAPTPTMTPA
Return 7, since the longest palindromic subsequence in the string is APTMTPA. Recall that a subsequence of a string does not have to be contiguous!
Your algorithm should run in O(n^2) time and space.