How do I efficiently determine the longest individual character palindrome in a given string?

Question

Given a string of length N containing characters [A-Z], how do I determine the longest palindrome for an individual character?

I will illustrate this with an example:

Given string: JOHNOLSON In analyzing the string, we find that we have a palindrome with the character O such that the string looks like JOHNOLSON. The palindrome for the O's is of length 7 essentially looking like O--O--O. Also, notice that there is a palindrome with N, but it is only of length 6.

Another example, Given string: ABCJOHNOLSON gives the same result as above with a palindrome of the O's of length 7 looking like O--O--O.

However, with the given string ABCJOHNOLSONDA, the longest individual character palindrome is of length 14 with the character A looking like A------------A.

Other simple examples include:

ABA --> A-A (length 3)

ABAXYZ --> A-A (length 3)

ABAXYZA --> A---A (length 5), not length 7 because A-A---A is not a palindrome for the letter A.

Pay special attention to the last example because it illustrates one of the subtle nuances of the problem.

Answer 1

You can do it in linear time, it's described here with a code sample.