Найти строку перестановки, которая имеет наибольшее количество подстрок палидромов

Question

Для моего класса Алгоритмы у меня есть следующее назначение;Это была домашняя работа по сортировке, поэтому я подозреваю, что должен использовать какой-то алгоритм сортировки.

Найти перестановку строк, в которой больше всего подстрок палиндромов.Входные данные N (длина строки) и строка s (1 < N < 2000).Выходные данные должны быть строкой, имеющей большинство палиндромных подстрок.(Если есть еще, которые содержат одинаковое количество, выведите любого).

Я попытался найти все перестановки и затем найти перестановку с большинством палиндромных подстрок, но есть ограничение по времени 1 с, и этокак я пересекаю этот предел.Кто-нибудь может помочь мне с этой задачей?

Это пример ввода:

ВХОД:

5
abccb

ВЫХОД:

bcacb (one of the outputs) 

ПримечаниеЯ также пытался найти структуру, которая дает больше всего подстрок палидромов, но этот путь не дал мне правильных результатов.

Answer 1

Я уже отвечал на аналогичный вопрос раньше, Как мы можем сделать максимальное количество палиндромных подстрок, переставляя символы в строке?

---

Наилучшая возможная перестановкастрока, которая дает максимальное количество палиндромов, может быть строкой sorted string.Возьмем, например, строку abcabc и пусть n обозначает размер строки в целом.

Мы можем переставить строку, чтобы сформировать палиндром abc|cba, который даст палиндромные подстроки длины n (все одиночные символы) + n / 2 (выбор подстроки через точку отражения) + {случаи, когда существуетпалиндром в любой точке отражения, которая в данном случае равна 0}.

Мы также можем переставить строку для формирования палиндромных пар вида (aa)(bb)(cc), что даст n (одинарные символы) + n / 2 (попарно подстрока) + {другие возможные палиндромные подстроки} палиндромы.

Точно так же можно сформировать 3-парный палиндром (aba)(cbc), и тогда число палиндромов будет равно n + n / 3 + {..}

Очевидно, что примы формируем более м-парный палиндром, количество палиндромных подстрок будет падать.Следовательно, мы должны рассмотреть Случай I и Случай II.Из этих двух вариантов лучше максимально использовать случай {other ..} для Case II путем увеличения плотности одинаковых символов, появляющихся вместе, как в случае отсортированной строки.Следовательно, отсортированная строка должна дать оптимальный ответ.

Следовательно, для вашего случая oolol -> llooo даст оптимальный результат 9, а gagadbcgghhchbdg -> aabbccddfgggghhh даст оптимальный результатиз 29, а также.Вы можете проверить любую строку, используя этот код: https://ideone.com/mMu2tq

def ispalin(s):
    return (s == s[::-1])

def cpalin(s):
    c = 0
    for i in range(len(s)):
        for j in range(i, len(s)):
            if ispalin(s[i:j + 1]):
                c += 1
    return c

print(cpalin(''.join(sorted("abccbaghghghgdfd"))))
print(cpalin(''.join(sorted("oolol"))))