0
$\begingroup$

The longest palindromic substring problem is certainly an interesting intellectual exercise, and seems to be popular in coding interviews in industry. As an interesting puzzle, its popularity for interviews is not too hard to understand--it's not too hard to find an $O(N^2)$ solution, and if someone manages to come up with a linear time solution, they're probably either a genius or at least well-read, which is arguably as valuable.

Given the apparent frivolity of the problem, however, it seems like a surprising amount of effort has gone in to analyzing it. There are at least three published linear-time solutions (by Manacher, Jeuring, and Gusfield). But, is it actually useful for anything? Are there other problems in which finding a palindromic substring is a necessary step? And in the absence of a direct application, did any of the known solutions to this problem reveal new techniques that have been applicable elsewhere?

$\endgroup$
4
$\begingroup$

Lots of string-related algorithms have applications in the field of bioinformatics. Motivations for finding palindromic substrings in bioinformatics include

  • Finding secondary structures in RNA folding 1

  • Predicting DNA breakage during gene conversion 2

  • Finding/analyzing clustered regularly interspaced short palindromic repeats (CRISPRs) 3

These three motivations are presented in an article here and there are most likely many more.

$\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.