Описание проблемы

Вам даны две строки A и B размера N и M соответственно. Вы должны найти количество всех перестановок A, присутствующих в B как подстроке. Вы можете предположить, что в строке будут только строчные буквы.

Ограничения проблемы: 1 ‹= N‹ M ‹= 105

Ввод: A = abc, B = abcbacabc

Выход: 5

Объяснение 1:

Permutations of A that are present in B as substring are:
    1. abc
    2. cba
    3. bac
    4. cab
    5. abc
    So ans is 5.

Здесь я объясню вопрос очень просто. Как вы уже читали вопрос, у нас есть две строки, в которых мы должны найти количество перестановок строки A в строке B, независимо от порядка символов, в котором она появляется в A.

Подход 1.

Первый подход заключается в том, что мы можем сгенерировать всю подстроку длины B в A, и мы можем проверить в каждой подстроке, что все символы B присутствуют в этой конкретной подстроке, если да, то мы можем увеличить счетчик и вернуть счетчик.

В этом случае сложность времени будет: O (n²) т.е. для генерации подстрок + O (m) для проверки всей подстроки, где n - длина B, а m - длина всей сгенерированной подстроки.

Подход 2.

Эту проблему легко решить с помощью хеширования и скользящего окна.

Главное наблюдение, необходимое для решения этой проблемы, заключается в том, что каждая перестановка строки будет иметь одинаковое количество символов и частота каждого символа в каждой перестановке будет одинаковой.

Итак, сначала мы можем создать хеш-карту размером 26, чтобы подсчитать частоту каждого символа в A.
После этого мы можем создать другую хеш-карту размером 26, чтобы подсчитать частоту каждого символ в первом окне размером N (длина A) в B, затем проведите по всем окнам, и когда оба хэша будут одинаковыми, мы можно сказать, что мы нашли перестановку A в B как подстроку.

Код:

Спасибо!