Задачи на строки — любимый полигон для алгоритмов: выглядят просто, но требуют точной модели стоимости. В этой теме мы нормализуем строки, проверяем палиндромы и анаграммы, группируем анаграммы и ищем самый длинный палиндром.
Модель стоимости
В Python str неизменяема. Каждый срез, lower(), replace() создаёт новую строку и тратит O(n) времени и памяти. А s[i] и len(s) стоят O(1). sorted(s) возвращает список символов за O(n log n), а Counter считает за O(n). Скрытая цена: s += c в цикле иногда даёт O(n^2) (об этом в следующей теме).
Нормализация и палиндром
Палиндром — строка, которая читается одинаково в обе стороны. В реальных текстах пробелы, знаки и регистр мешают сравнению, поэтому сначала нормализуем: оставляем только буквы-цифры и приводим к нижнему регистру. Затем t == t[::-1].
