Find all substrings of a string that are a permutation of another string

Find all substrings of a string that contains all characters of another string. In other words, find all substrings of the first string that are anagrams of the second string.

Please note that the problem specifically targets substrings that are contiguous (i.e., occupy consecutive positions) and inherently maintains the order of elements.

 
For example,

Practice this problem

The idea is to maintain a sliding window of size m, where m is the length of the second string. At any point, the sliding window would contain a substring of the first string of size m. At each iteration of the loop, remove the leftmost element from the sliding window and add the next character of the first string to it, so it points to the next substring of the first string.

At each point the window changes, compare the window’s characters with that of the second string. If all characters in the current window match that of the second string, we have found an anagram. After all substrings of the first string are considered, i.e., the window reaches the first string’s last character, the process terminates.

Following is the C++ and Java implementation based on the above idea:

The time complexity of this solution would be O((n – m) × m) as there are n-m substrings of size m, and it takes O(m) time and O(m) space to check if they are anagrams or not. Here, n and m are lengths of the first and second strings, respectively.

 
We can also solve this problem using std::is_permutation in C++, which determines if a sequence is a permutation of another sequence.