h2. Largest palindrome

bq. Given a string of length n, find out it's largest palindromic substring.

bq. Given a string of length n, find out it's largest palindromic subsequence.

The naive solution is O(n^3^). For every possible substring it tests in linear time if it's a palindrome.

The naive solution is O(n^3^). For every possible subsequence it tests in linear time if it's a palindrome.

A smarter solution tries every position in the original string as the center of a palindrome and extends to the left and to the right as long as the corresponding characters match. This solution takes O(n^2^) time.