How to effectively determine the longest individual character palindrome in a given line?

Question

For a string of length N containing the characters [AZ], how to determine the longest palindrome for a single character?

I will illustrate this with an example:

The specified string: JOHNOLSON When analyzing the string, we find that we have a palindrome with the character O , so that the string looks like J O HN O LS O N The palindrome for O has a length of 7, essentially looking like O -- O -- O Also note that there is a palindrome with N , but it has a length of 6.

Another example, This line: ABCJOHNOLSON gives the same result as above, with an O palindrome of length 7, similar to O -- O -- O

However, with this line ABCJOHNOLSONDA , the longest individual palindrome has a length of 14 with a character A similar to 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 not a palindrome for the letter A

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

Answer 1

You can do this in linear time, he described here with sample code.

Answer 2

This is what I came up with; I do not know how effective it is.

 For every letter in the alphabet,
     Find the first and last occurrence of this letter.
     While the substring is not a palindrome for that letter (easy to check),
     find the next letter on both sides so that every possible combination is
     checked.  Take the longest one and store it.
 Take the longest one.

Answer 3

Definitely not optimal. Assumes the string you enter is lowercase.

 using System; using System.Collections.Generic; public class LongestPalindrome { public int longest(string s) { Dictionary<char, List<int>> indices = new Dictionary<char, List<int>>(); // find all indices for each letter for (int i = 0; i < s.Length; i++) { char c = s[i]; if (!indices.ContainsKey(c)) indices.Add(c, new List<int>()); indices[c].Add(i); } int max = Int32.MinValue; for (int i = (int)'a'; i <= (int)'z'; i++) { char c = (char)i; // in case a letter didn't appear at all in the input string if (!indices.ContainsKey(c)) continue; List<int> indexList = indices[c]; // in case a letter appeared only once in the input string if (indexList.Count == 1) max = Math.Max(max, 1); for (int j = 0; j < indexList.Count; j++) { for (int k = j + 1; k < indexList.Count; k++) { int dist = indexList[k] - indexList[j] + 1; string sub = s.Substring(indexList[j], dist); if (isPalendrome(sub, c)) max = Math.Max(max, dist); } } } return max; } bool isPalendrome(string s, char c) { int i = 0; while(i < s.Length - 1 - i) { if (s[i] != c && s[s.Length - 1 - i] != c) { i++; continue; } if (s[i] != s[s.Length - 1 - i]) return false; i++; } return true; } }