Друзья, разбираем вчерашнюю задачу.
Задача на составление палиндрома наибольшей длины — это классическая задача, основанная на идее подсчета. Очень многие задачи в программировании решаются подсчетом.
Идея алгоритма. Подсчитаем количество всех букв в исходной строке и сохраним его в списке
Обратите внимание, что приведенное решение не использует сортировку, множества и словари. Его временная сложность является линейной (то есть
#разборзадач #задачанакод #собеседование
Задача на составление палиндрома наибольшей длины — это классическая задача, основанная на идее подсчета. Очень многие задачи в программировании решаются подсчетом.
Идея алгоритма. Подсчитаем количество всех букв в исходной строке и сохраним его в списке
counters. Поскольку латинских букв всего 26, то длина списка будет равна 26, то есть требуется константное количество дополнительной памяти. Так как по условию нужно вывести первый палиндром в алфавитном порядке, то конструирование искомого палиндрома будем начинать буквой A и заканчивать буквой Z. И не забываем про центральный элемент палиндрома, который может не иметь парного элемента.Обратите внимание, что приведенное решение не использует сортировку, множества и словари. Его временная сложность является линейной (то есть
O(n), где n — количество символов в исходной строке).#разборзадач #задачанакод #собеседование