Ctrl K

Выровнять частоты букв

Средняя
Дана строка text из строчных латинских букв и целое число slack. Посчитаем для каждой буквы, которая есть в строке, сколько раз она встречается. Назовём строку ровной, если любые две такие частоты отличаются не больше чем на slack. Из строки можно удалять символы. Если буква удалена целиком, её частота больше не учитывается. Верните наименьшее число удалений, после которых строка станет ровной.
Пример 1
text="banana", slack=0 → 2

Частоты: a — 3, n — 2, b — 1. Уберём b и одну a: останутся по две a и n.

Пример 2
text="mississippi", slack=1 → 3

Частоты: m — 1, i — 4, s — 4, p — 2. Например, убираем m, одну i и одну s: частоты 3, 3 и 2 отличаются не больше чем на 1.

Пример 3
text="abc", slack=0 → 0

Каждая буква встречается по разу, строка уже ровная.

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

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