longest palindromic subsequence / substring and dynamic programming
Finding substring palindromes of maximum size can be solved in linear time in several ways. Right now come to my mind solutions using data structure such as:
- Manacher
- Palindromic Tree
- Binary search + (Hashing or suffix array) (not really linear but almost, $O(n \cdot \log n)$

If you let me use prewritten code to solve this problem I'd choose first option, is probably the faster and easy way, but personally I don't feel comfortable implementing Manacher from scratch.

I'll try to expand in the binary search + hashing solution. 

First let's solve the subproblem: is it substring from a to b a palindrome? If you use rolling hash you will be able to determine hash of substring in O(1), so you can hash the string and it's reverse, and ask whether a substring and it's reversed counterpart match in hash. Notice that this solution is susceptible to fail due to hashing collisions, and one way to address this is using some more elaborated data structure such as suffix array.

After having such function, you can binary search over the length of the palindrome, this is: fix a length k, then go over every substring of length k and check whether it is or not a palindrome. 

It has a problem, and it is that function is not monotone over k, but this happens because odd palindromes are not contained in even palindromes necessarily, and vice versa. To address this just run two binary search, first over even integers, and second one over odd integers.