Задача Яндекса.
Обязательно реши эту задачу если идешь в Яндекс.

Не могу не поделится задачей, которую крутят уже пятый раз подряд.
Задача называется Permutation in String.
В задаче говорится, что дается две строки s1 и s2 и нужно вернуть true если в s2 существует подстрока, которая является перестановкой строки s1.

Единственное собеседующий скажет что в строках могут быть абсолютно любые символы (то есть не только латинские буквы)

Решение:
Первое решение, которое попросят улучшить:
Давайте в словаре d1 посчитаем то сколько раз встречается каждая буква в s1.
Теперь наша задача, найти такой i, что Count(s2[i, i + len(s1) - 1]) = d1.
Для этого мы могли бы хранить второй словарь d2 где будем хранить вхождения букв на подотрезке длины len(s1) и обновлять значения ключей (делаем +1 и -1 к буквам s[i] и s2[i - len(s1)] соответственно)

Сложность такого алгоритма O(n * min(len(s1), m) где m - количество различных букв в строках.
Вы могли подумать откуда тут произведение ?
Произведение возникает из за того что мы на каждом шагу сравниваем две хеш-тиблицы.

Второе решение:
Обойдемся только одной хеш таблицей, чтобы не сравнивать на каждом шаге две хеш таблицы как мы это делали выше.
Посчитаем словарь d1 также как и выше для строки s1.
Теперь проходится по строке s2 окошкой длины len(s1) и мы когда делаем -1 и +1 для букв s2[i] и s2[i - len(s1)] соответственно, таким образом храня в словаре разницу!
Когда значения какого-то ключа обнулилось мы должны удалить этот ключ.
Когда словарь становится пустым (то есть len(d1) == 0) мы нашли нужный подотрезок.
Сложность алгоритма O(n)

Код в комментариях.