1
$\begingroup$

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?

$\endgroup$
3
  • 2
    $\begingroup$ Why do you not consider it a DP solution? $\endgroup$ – Dmitri Urbanowicz Dec 16 '19 at 4:32
  • $\begingroup$ 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). $\endgroup$ – Alan Evangelista Dec 16 '19 at 5:06
  • 1
    $\begingroup$ 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. $\endgroup$ – Dmitri Urbanowicz Dec 16 '19 at 7:12
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.