Раскладка на девяти кнопках

Средняя

Вы проектируете кнопочный телефон с девятью кнопками и сами решаете, какие строчные латинские буквы на какую кнопку поставить. Условия такие: - каждая из 26 букв стоит ровно на одной кнопке; - на одной кнопке не больше трёх букв. Чтобы набрать букву, стоящую на кнопке k-й по счёту, кнопку нажимают k раз подряд. Дан текст text. Раскладку выбирают один раз, а потом набирают на ней весь текст. Верните наименьшее возможное общее число нажатий.

Пример 1

text="tomato" → 6

Разных букв всего четыре, каждую можно поставить первой на свою кнопку. Шесть букв — шесть нажатий.

Пример 2

text="abcdefghijj" → 12

Разных букв десять. j встречается дважды, её ставим первой на кнопку (2 нажатия). Ещё восемь букв тоже первые (8 нажатий), а последней достаётся второе место на какой-то кнопке (2 нажатия). Итого 12.

Ограничения

1 ≤ len(text) ≤ 10⁵
text состоит из строчных латинских букв

Встречал эту задачу на настоящем собесе?

Решили0

Пробовали0

Отправок0

Принято—

Темы

Greedy Hash Table String Counting Sorting

Вход

text="tomato"

Ожидается

«Запустить» — первые 3 теста у тебя в браузере, «Отправить» — все 78 тестов на сервере, включая скрытые.