Как мы можем создать максимальное количество палиндромных подстрок, переставляя символы в строке? - PullRequest
Новая
       51

Как мы можем создать максимальное количество палиндромных подстрок, переставляя символы в строке?

0 голосов
/ 17 октября 2018

Строка называется подстрокой другой строки, если она может быть получена из этой строки путем удаления некоторого (возможно, нулевого) количества символов в начале и в конце.

Например, abc, ab и c - это подстроки строки abc, тогда как ac и d - нет.

Давайте определимЧисло палиндромных строк как число ее подстрок, являющихся палиндромами.

Например, число палиндромных строки aaa равно 6, потому что все ее подстроки являются палиндромами.И число палиндромов для строки abc равно 3, потому что палиндромами являются только ее подстроки длины 1.

Итак, еще два примера:

  1. если строка -> oolol

    answer = ololo,  9 substrings can be formed
'o', 'l', 'o', 'l', 'o', 'olo', 'lol', 'olo', 'ololo'

  2. если строка -> gagadbcgghhchbdg

    answer = abccbaghghghgdfd, 29 substrings can be formed

Вам дана строка s.Вы можете произвольно переставлять своих персонажей.Ваша цель - получить строку с максимально возможным значением числа палиндромов.

1 Ответ

0 голосов
/ 17 октября 2018

Наилучшая возможная перестановка строки, которая дает максимальное количество палиндромов, может быть таковой для 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"))))
...