# longest palindromic subsequence / substring and dynamic programming

The longest palindromic subsequence problem can be solved using dynamic programming because it is recursive and has overlapping subproblems, as described in https://www.geeksforgeeks.org/longest-palindromic-subsequence-dp-12/ .

On the other hand, AFAIK there is no dynamic programming solution to the longest palindromic substring problem. In the DP solution presented at https://www.geeksforgeeks.org/longest-palindrome-substring-set-1/ , the overall solution is equal to the naive one: to compare the length of all palindromic substrings. The only difference is that DP is used to speed up the process of finding if each substring is palindromic, which reduces the time complexity from O(n^3) (naive solution) to O(n^2).

Why is there a DP solution for the LP subsequence problem, but not for the substring problem? Is it because the former can be expressed by a recursion and the latter not?

• Why do you not consider it a DP solution? – Dmitri Urbanowicz Dec 16 '19 at 4:32
• Maybe I was not clear enough. I meant a DP solution in which the size of the longest palindrome substring is saved for each substring (similar to the DP solution for the longest palindrome subsequence, which saves the size of the LPS for all subsequences which start in i and end in j, 0 <= i <= j < string_size). – Alan Evangelista Dec 16 '19 at 5:06
• it’s because if you know that there’s a palindrome in any given substring, but don’t know where it is, you won’t be able to reason about their concatenations. – Dmitri Urbanowicz Dec 16 '19 at 7:12

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)$$