CODEWITHSUNDEEP
algorithmpalindrome
jbranchaud
jbranchaud

Reputation: 6087

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

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.

Upvotes: 8

Views: 402

Answers (3)

SundayMonday
SundayMonday

Reputation: 19767

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;
    }
}

Upvotes: 0

Ry-
Ry-

Reputation: 225281

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.

Upvotes: 0

Jordan Bentley
Jordan Bentley

Reputation: 1309

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

Upvotes: 5

Related Questions