Find the longest non-palindromic substring in a string

Question

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?

Answer 1

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.