Ctrl K

Подстроки, вмещающие набор букв

Средняя
Даны две строки: text и kit. Строка kit — это набор букв (с учётом повторов). Подстрока text подходит, если из её букв можно выложить весь набор: каждая буква встречается в подстроке не реже, чем в kit. Иными словами, буквы подстроки можно переставить так, чтобы она начиналась с kit. Посчитайте, сколько непустых подстрок text подходят. Подстроки в разных позициях считаются разными.
Пример 1
text='cabd', kit='ab' → 4

В подстроке должны быть хотя бы одна «a» и одна «b». Подходят «ab», «cab», «abd» и «cabd».

Пример 2
text='abab', kit='aaa' → 0

Во всей строке только две «a», а нужно три, — ответ 0.

Пример 3
text='zzz', kit='z' → 6
Ограничения
  • 1 ≤ len(text) ≤ 10⁵
  • 1 ≤ len(kit) ≤ 10⁴
  • Обе строки состоят из строчных латинских букв
Встречал эту задачу на настоящем собесе?
Решили0
Пробовали0
Отправок0
Принято—
Темы
Похожие задачиСамый длинный фрагмент без повторов СредняяОтрезок из двух букв СредняяПовторяющиеся участки гена СредняяОкно с ограниченным набором букв СредняяКаждая буква не реже k раз Средняя
загружаем Python…
Вход
text='cabd', kit='ab'
Ожидается
4

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