Условия задачи на нахождение длины самого длинного палиндрома из символов строки

Что проверяют

Уточняете ли вы условие до того, как начали писать код. Формулировка про самый длинный палиндром из символов строки допускает три разные задачи с разными решениями, и интервьюер смотрит, спросите ли вы или броситесь кодить первое, что вспомнили.

Как отвечать

Сначала разведите варианты вслух:

• собрать палиндром из имеющихся символов, порядок не важен, нужна только длина;
• найти самую длинную палиндромную подстроку, то есть непрерывный кусок;
• найти самую длинную палиндромную подпоследовательность, символы идут по порядку, но с пропусками.

Первая решается коротко: от каждой частоты берём чётную часть, и если хоть одна нечётная, добавляем символ в центр.

fun longestPalindrome(s: String): Int {
    val counts = s.groupingBy { it }.eachCount().values
    val pairs = counts.sumOf { it / 2 }
    val hasOdd = counts.any { it % 2 == 1 }
    return pairs * 2 + if (hasOdd) 1 else 0
}

Это один проход и память по размеру алфавита. Для подстроки основной приём это расширение от центра: по каждой позиции два прохода, для нечётного и чётного случая, время квадратичное. Линейный алгоритм Манакера обычно достаточно назвать. Подпоследовательность решается динамическим программированием по отрезкам.

Проговорите краевые случаи: пустая строка, один символ, все символы разные, учитывается ли регистр. Примеры для проверки приводите сразу, это часть ответа.

Где спотыкаются

Пишут расширение от центра и называют его линейным. Оно квадратичное: центров столько же, сколько позиций, и от каждого расширение идёт вплоть до краёв строки. Неверно названная сложность стоит дороже, чем честное «квадрат, про линейный знаю по названию».

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

Третье: в Kotlin забывают, что строка это последовательность единиц UTF-16. Перебор по индексам режет пополам символы вне основной плоскости, и на эмодзи функция начинает врать. Если во входе возможен произвольный текст, скажите об этом сами.