Longest Palindromic Substring-Dynamic Programing

Longest Palindromic Substring

Given a string S, find the longest palindromic substring in S.
           

Analysis:

First think how we can avoid unnecessary re-computation in validating palindromes. Consider the case

"ababa". If we already knew that "bab" is a palindrome, it is obvious that "ababa" must be a palindrome

since the two left and right end letters are the same.

Reference:

Longest Palindromic Substring