Day 396

[vaskoz]

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.