Longest Palindrome

Q: Какова временная сложность алгоритма поиска самого длинного палиндрома?

Время O(n) при подсчёте: каждая буква добавляет 1 к одному счётчику, а суммирование пар требует прочитать 128 счётчиков независимо от длины s . Затраты памяти — O(1) . Сортировка и объединение соседних элементов в пары требуют времени O(n log n) и памяти O(n) .

ЛегкоХеширование Жадные алгоритмы

+10

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

Заглавные и строчные буквы считаются разными, поэтому Aa — не палиндром.

Функция

longestPalindrome(s: string) → integer

sstring: буквы, которые вы можете использовать, в верхнем и нижнем регистре
Возвращаетinteger: длина самого длинного палиндрома, который можно составить из этих букв

Ограничения

1 ≤ s.length ≤ 5 × 10⁴
s содержит только английские буквы: от a до z и от A до Z.
Необязательно использовать все буквы.

Примеры

Ввод: s = "coddyCode"
Вывод: 5
Пояснение: o встречается дважды, а d — три раза, остальные буквы — по одному разу. Пара букв o, пара букв d и одна оставшаяся буква посередине дают длину 5, например doCod.

Ввод: s = "Aa"
Вывод: 1
Пояснение: A и a — разные буквы, поэтому такой пары не существует. Одна буква сама по себе является палиндромом длины 1.

Ввод: s = "xxxyyy"
Вывод: 5
Пояснение: Две буквы x и две буквы y образуют пары, а одна оставшаяся буква помещается посередине, как в xyxyx. У последней буквы y нет пары, поэтому она остаётся за пределами.

Дополнительный вопрос

Можете ли вы вернуть самую длинную палиндромную подстроку вместе с её длиной, по-прежнему за время O(n)?

Подсказки

Открывайте по одной. Каждая подсказывает чуть больше.

Открыто 0 из 3

Решение

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

Отсортируйте и объедините соседние элементы в пары

Идея

Сортировка ставит одинаковые буквы рядом, поэтому каждая пара оказывается бок о бок. В xxxyyy буквы x на позициях 0 и 1 совпадают: возьми пару и переместись на две позиции. На индексе 2 x и y различаются, поэтому эта x остаётся без пары, и ты перемещаешься на одну позицию. Буквы y на позициях 3 и 4 образуют вторую пару, а последняя y остаётся одна. Две пары дают 4, плюс одна средняя буква: 5.

Буква остаётся лишней ровно тогда, когда в парах использовано меньше, чем все n букв, поэтому отдельный флаг не нужен. Сортировка требует времени O(n log n), а отсортированная копия занимает O(n) памяти.

Алгоритм

Отсортируй буквы в s.
Пройди по отсортированным буквам, используя индекс i. Если буквы в позициях i и i+1 одинаковые, прибавь 2 к длине и переместись на две позиции; в противном случае переместись на одну позицию.
Если длина меньше количества букв, прибавь 1 за среднюю букву.
Верни длину.

def longestPalindrome(s):
    letters = sorted(s)
    n = len(letters)
    length = 0
    i = 0
    while i + 1 < n:
        if letters[i] == letters[i + 1]:
            length += 2  # a pair: one copy on each side of the middle
            i += 2
        else:
            i += 1
    # A letter left without a partner can stand alone in the middle
    if length < n:
        length += 1
    return length

Подсчитайте каждую букву

Идея

Подсчёт даёт ту же информацию без сортировки. Заведите по одному счётчику для каждого кода символа — всего 128, поэтому A и a попадут в разные счётчики. Буква, встречающаяся c раз, даёт c, округлённое вниз до ближайшего чётного числа, букв.

Для coddyCode пары o и d дают 4 буквы. Пять букв остаются неиспользованными, и любая из них может стоять посередине: 5. У второй непарной буквы не было бы зеркальной пары.

Один проход по s заполняет счётчики, а один проход по 128 счётчикам суммирует пары: время O(n) и дополнительная память O(1) (в R — O(n), поскольку сначала s преобразуется в вектор кодов).

Алгоритм

Создай 128 счётчиков, установленных на 0, и прибавляй 1 к счётчику каждой буквы из s.
Для каждого счётчика прибавь к длине значение счётчика, округлённое вниз до чётного числа.
Если длина меньше длины s, значит, какое-то значение счётчика нечётное, поэтому прибавь 1 для средней буквы.
Верни длину.

def longestPalindrome(s):
    counts = [0] * 128  # one counter per character code, so 'A' and 'a' differ
    for ch in s:
        counts[ord(ch)] += 1
    length = 0
    for count in counts:
        length += count // 2 * 2  # every pair fits, one copy on each side
    # Fewer letters used than s has: some count is odd, so one letter can go in the middle
    if length < len(s):
        length += 1
    return length

Ловушки и крайние случаи

Полностью исключать нечётное количество. Буква, которая встречается 3 раза, всё равно даёт одну пару: xxxyyy даёт 5, а не 1.
Добавлять 1 за каждое нечётное количество. В середине может быть только одна буква, поэтому xxxyyy даёт 5, а не 6.
Считать A и a одной и той же буквой. В Aa нет ни одной пары, поэтому ответ — 1, а не 2.
Задавать размер счётчиков только для символов от a до z. Коды заглавных букв — от 65 до 90, поэтому они не входят в этот диапазон; используйте в качестве индекса полный код символа.

Частые вопросы3

Чем задача «Самый длинный палиндром» отличается от задачи «Самая длинная палиндромная подстрока»?

Здесь можно переставлять буквы, поэтому важны только их количества, и подсчёт решает задачу за O(n). Задача Longest Palindromic Substring требует найти палиндром, который уже встречается как блок подряд идущих букв, и для этого нужен другой метод, например расширение вокруг каждого центра. Для abab эта задача даёт ответ 4 (abba), а задача о подстроке — 3 (aba).

Какова временная сложность алгоритма поиска самого длинного палиндрома?

Время O(n) при подсчёте: каждая буква добавляет 1 к одному счётчику, а суммирование пар требует прочитать 128 счётчиков независимо от длины s. Затраты памяти — O(1). Сортировка и объединение соседних элементов в пары требуют времени O(n log n) и памяти O(n).

Нужно ли использовать каждую букву из s?

Нет. В середину входит каждая пара, а также не более одной непарной буквы. Поэтому ответ — длина s, если не более чем у одной буквы нечётное количество вхождений; в противном случае — длина s минус количество букв с нечётным количеством вхождений плюс 1.

def longestPalindrome(s):
    # Напишите код здесь

Тест #1

Тест #2

Тест #3

Аргумент

s = "coddyCode"

Ожидаемый вывод