Ctrl K

Перераскладка кнопочного телефона

Средняя
На старом кнопочном телефоне буквы набираются клавишами 2–9. На каждую клавишу назначен свой набор букв: чтобы ввести первую букву набора, клавишу нажимают один раз, вторую — два раза, и так далее. Вы можете заново распределить буквы по клавишам как угодно: каждой букве — ровно одна клавиша и место в её наборе, на клавише может быть сколько угодно букв (или ни одной). Клавиши 0, 1, * и # букв не содержат. Дана строка text из строчных латинских букв. Подберите раскладку так, чтобы набор text потребовал как можно меньше нажатий, и верните это число.
Пример 1
text="banana" → 6

Три буквы — на три разные клавиши первым нажатием: 3 + 2 + 1 = 6.

Пример 2
text="abcdefghij" → 12

Восемь букв встают первыми на восемь клавиш, оставшиеся две — вторыми: 8·1 + 2·2 = 12.

Пример 3
text="qqqq" → 4
Ограничения
  • 1 ≤ len(text) ≤ 10⁵
  • text состоит из строчных латинских букв
Встречал эту задачу на настоящем собесе?
Решили0
Пробовали0
Отправок0
Принято—
Темы
Похожие задачиБез одинаковых соседей СредняяРаскладка на девяти кнопках СредняяПалиндромы из общих букв СредняяЗаполнить пропуски с минимумом повторов СредняяВыровнять частоты букв Средняя
загружаем Python…
Вход
text="banana"
Ожидается
6

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