Разбор задачи 409 на LeetCode

При решении задач на LeetCode наткнулся на задачу номер 409. Кратко о задаче: дана строка, нужно найти максимальную длину палиндрома, который можно составить из её символов. Чтобы решить эту задачу потребовалось детальнее разобраться в сущности палиндрома.

Начнем с общего определения: палиндром — это строка текста, которая слева направо и справа налево одинаково. Главное правило — при построении палиндрома из имеющихся символов все символы должны быть парными, кроме, возможно, одного в центре.

Например, строка «aa» или «aba» — корректные палиндромы. У нас есть две парные буквы «a» в обоих примерах. И одиночная буква «b» посередине.

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

На первый взгляд кажется, что мы можем просто взять и посчитать частотность символов в строке. То есть:

1. c — 4 раза
2. d — 2 раза
3. a — 1 раз
4. b — 1 раз

Итого получаем 8. Но правильный ответ 7. Давайте разберемся почему.

У нас есть 6 букв, частотность которых является четным числом. Это буквы «c» и «d». А так же остаются буквы «a» и «b». Мы можем взять только ОДНУ из них, чтобы поставить ее в центре. Соответственно, берем любую из них. В случае решения задачи это выглядит как инкремент итоговой максимальной длины палиндрома.

Итоговый алгоритм решения задачи:

1. Посчитать частоты символов
2. Суммировать все чётные частоты
3. Из нечётных взять частота — 1
4. Если были нечётные — добавить 1

Примечание касательно 3 и 4 пунктов. Из нечётного количества (например, 3) мы берём только чётную часть (2) — она пойдёт в пары. Один символ остаётся. Таких «остатков» может быть много, но в палиндром можно поставить только один символ в центр. Поэтому в конце прибавляем 1, если были нечётные.

Пример кода решения задачи на PHP:

class Solution {
    function longestPalindrome($s) {
        $strArray = array_count_values(str_split($s));
        $length = 0;
        $hasOdd = false;
        foreach($strArray as $count) {
            if($count % 2 == 0) {
                $length += $count;
            } else {
                $length += $count - 1;
                $hasOdd = true;
            }
        }
        if($hasOdd) $length += 1;
        return $length;
    }
}