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

8
votes

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.

3
algorithmpalindrome
There has to be a better term for what you're looking for than "palindrome" because most of your examples aren't palindromes. - Blastfurnace
Consider an example string ABCDAEEALMNA that when considering the A's would look like A---A--A---A which is a palindrome (when you ignore the uniqueness of the rest of the characters) of size 12, but consider the string ABCDAEEALMNOA of which the whole string is no longer a palindrome, instead a much smaller substring becomes the longest palindrome, namely A---A of length 5 on the end. - jbranchaud
I understand the pattern you are interested in, it just doesn't fit the dictionary definition of the term palindrome. I wonder if there is a regular expression solution for what you're seeking. - Blastfurnace
@BlastFurnace I understand what you are saying. Would you suggest a different way of thinking about the problem? It presented itself to me as a palindrome, so I am not sure what else it could be described as. - jbranchaud

3 Answers

5
votes

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

0
votes

Here's what I came up with, I don't know how efficient it might be.

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.
0
votes

Definitely not optimal. Assumes input string is all 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;
    }
}