Игра в строки

Пусть массив $$$a_i$$$ — количество $$$i$$$-х букв алфавита, которое есть во второй строке. Зафиксируем подстроку длины $$$k$$$ первой строки. Пусть массив $$$b_i$$$ — количество $$$i$$$-х букв алфавита, которое есть в этой подстроке. Тогда надо проверить, что существует подстрока, для которой $$$b_i \le a_i$$$ для всех $$$i$$$ от $$$1$$$ до $$$26$$$.

Посчитаем массив $$$a$$$ за $$$O(|t|)$$$. Также посчитаем массив $$$b$$$ для подстроки длины $$$k$$$ первой строки, начинающейся в первом символе. Заметим, что при переходе от одной подстроки к следующей, в массиве $$$b$$$ изменяется не более двух элементов, а значит этот переход делается за $$$O(1)$$$.

Тогда построить массив $$$b$$$ для всех подстрок длины $$$k$$$ первой строки можно за $$$O(|s|)$$$. Проверить каждую из них занимает $$$O(26)$$$ времени, где $$$26$$$ — размер алфавита. Тогда всё решение работает за $$$O(26|s| + |t|)$$$.