Как эффективно определить самый длинный отдельный символ палиндрома в данной строке?

Question

Для строки длиной N, содержащей символы [AZ], как определить самый длинный палиндром для отдельного символа?

Я проиллюстрирую это на примере:

Данная строка:JOHNOLSON Анализируя строку, мы обнаруживаем, что у нас есть палиндром с символом O, такой что строка выглядит как JOHNOLSON.Палиндром для O имеет длину 7, по существу похожую на O--O--O.Кроме того, обратите внимание, что есть палиндром с N, но он имеет только длину 6.

Другой пример, учитывая строку: ABCJOHNOLSON дает тот же результат, что и выше, с палиндромом OДлина 7 выглядит как O--O--O.

Однако сзаданная строка ABCJOHNOLSONDA, самый длинный отдельный символ палиндрома имеет длину 14 с символом A, похожим на A------------A.

Другие простые примеры:

ABA -> A-A (длина 3)

ABAXYZ -> A-A (длина 3)

ABAXYZA -> A---A (длина 5), а не длина 7, так как A-A---A не является палиндромом для буквы A.

Обратите особое внимание на последний пример, поскольку он иллюстрирует один из тонких нюансов пРОБЛЕМА.

Answer 1

Вы можете сделать это за линейное время, это описано здесь с примером кода.

Answer 2

Определенно не оптимально. Предполагается, что входная строка строчная.

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

Answer 3

Вот то, что я придумал, я не знаю, насколько это может быть эффективно.

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.