Find the longest non-palindromic substring in a string

3
votes

I need to find out the longest non-palindromic substring ( a string which itself isn't a palindrome, doesn't matter whether any substring of it is) in a string, in O(n**2) or less time.

I can come up with the simple brute force algorithm, finding all possible substrings (O(n ** 2)), then for each such substring checking if that is a palindrome (O(n)), taking the overall complexity to O(n**3).

There are O(n**2) variants of finding out longest palindromic substring and sequence, but I am unable to reuse them to find out the solution here.

How do I do it in O(n**2) time?

2
stringalgorithmpalindrome
Hint: if you remove the first character from a palindrome, you get something that isn't a palindrome - except for one very specific family of cases that is easy to detect. - John Dvorak
What is a non-palindromic substring? A substring that isn't itself a full palindrome? Because in that case the problem sounds pretty simple. Try to work it out on paper with a few examples. - biziclop
Edited question. Yes Jan, I know. The specific set is what that is bothering me. - SexyBeast
Why's that specific set bothering you? Tell me, what do you think the set is? - John Dvorak
As far as I can see, there are variety of ways I can get a non-palindromic substring from the longest palindromic one - adding characters at the beginning or at the end, removing characters from the beginning within, or from the end, or doing both. Can't figure out. - SexyBeast

2 Answers

7
votes

Since there's an answer posted already, let me turn my hints into an actual answer:

First, check if the full string is:

  • a palindrome (O(n), with O(1) average case)
  • a repetition of the same character, such as "aaaaaaaaaaaa" (done in the same loop).

Then:

  • if the string isn't a palindrome, the longest non-palindrome substring is the string itself
  • if the string is a palindrome but not a repetition of the same character, then removing either end will make it a non-palindrome, and the longest such substring
  • if the string is a repetition of the same character, then it has no non-palindrome substring. Alternatively, depending on your definition of palindrome, the only non-palindrome substring is the empty substring.
-2
votes

Let s,e be positions in the strings.

You can tell if the substring s,e is palindrom by checks string[s] == string[e] and the substring s+1, e-1 is also palindrom (special case single chars s==e and empty stringss>e to true).

So the easiest implementation is to make a recursive function as described above and memoize the results (store them in a external matrix).

You can also do it iteratively if you are careful with your iteration (so that you only need results previously computed).

Both will populate O(N^2) and the individual computations are trivial.