2
$\begingroup$

The problem requires us to find the substring within a string which happens to be a palindrome. Multiple palindromes are also allowed.
For example, in "LODHIHDAK" "DHIHD" is a palindrome.

Comparing the reversed string with the original string to identify the common substring is one way but it isn't fool-proof.

For example,
In the case of "KLXABAXYC", it would work.
But in the case of "ABACDGFDCABA", it would not.

I was wondering if brute force could be used but I don't understand how.
I'm looking to find the longest palindrome.

$\endgroup$
  • 1
    $\begingroup$ What do you mean by "find palindrome within a string"? Try to be more verbose. Don't assume we are familiar with your problem. $\endgroup$ – Yuval Filmus Jul 8 at 21:39
  • 3
    $\begingroup$ Do you want to find all palindromes? Only the longest? Only the first? $\endgroup$ – reinierpost Jul 9 at 18:34
2
$\begingroup$

Of course, every letter is a one letter palindrome - so let's assume you are looking for a palindrome that is at least two letters long.

If your goal is just to find any palindrome in a string $\{a_i\}$(rather than finding all palindromes or finding the longest palindrome, for example) then you only need to consider two cases:

1) If $a_n=a_{n+1}$ for any $n$ then you have found a two letter palindrome.

2) If $a_n=a_{n+2}$ for any $n$ then you have found a three letter palindrome.

Any longer palindrome must contain a two or a three letter palindrome as a substring.

$\endgroup$
  • $\begingroup$ Thank you! I'll try it out $\endgroup$ – Neha Tirumalasetti Jul 9 at 18:21
  • $\begingroup$ This is the O(n^2) dynamic programming algorithm that is quite fast in practice. There exists a O(n) algorithm known as Manacher's algorithm as well $\endgroup$ – hLk Jul 15 at 17:45
0
$\begingroup$

Your solution only works in the cases where the midpoint of the palindrome is the middle point of the string. You can use the more general following approach:

Consider each letter of the string to be the midpoint of a palindrome. Then look to the left and to the right of the current letter and check if the characters match. If they do check if the next pair of characters match. If they do not, consider the next character as the midpoint.

For example, consider the sting AEBCDCBGGGGG

You first consider the first $A$ to be the midpoint. Since it has no character to the left it cannot be a midpoint. You move on to the second letter, $E$ and consider it to be the midpoint. Next, you compare $A$ and $B$. Since they are not the same $E$ is not the midpoint of a palidrome. You consider $B$ as a midpoint. Again since $E$ and $C$ are not the same, $B$ cannot be the midpoint of a palindrome. After some steps, you will consider $D$ as a midpoint. This time its neighbouring letters are $C$ and $C$, therefore, $D$ is the midpoint of a palindrome. You move on to the next letters which are $B$ and $B$, so they are part of the palindrome. The next letters are $E$ and $G$, therefore they are not part of a palindrome. So you know that the string contains at least one palindrome, BCDCB. You continue traversing the string in the same way looking for more palindromes.

$\endgroup$
  • $\begingroup$ Thank you! This solves my problem $\endgroup$ – Neha Tirumalasetti Jul 9 at 18:22

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.