Описание проблемы
Вам даны две строки 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 как подстроку.
Код:
Спасибо!