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

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

 

For example,


string str1 = ‘XYYZXZYZXXYZ’;
string str2 = ‘XYZ’;


Anagram ‘YZX’ present at index 2
Anagram ‘XZY’ present at index 4
Anagram ‘YZX’ present at index 6
Anagram ‘XYZ’ present at index 9

 


 

The idea is to use sliding window of size m where m is the length of the second string. So at any point of time, the sliding window would contain a substring of first string of size m. At each iteration of the loop, we remove leftmost element from the sliding window and add next character of first string to it so it points to next substring of X. At each point the window changes, we compare window’s characters with that of second string. If all characters in current window matches that of second string, we found an anagram. The process terminates when we have considered all substrings of first string. i.e. window reaches the last character of the first string.

 
C++ implementation –
 

Download   Run Code

Output:

Anagram YZX present at index 2
Anagram XZY present at index 4
Anagram YZX present at index 6
Anagram XYZ present at index 9

 

The time complexity of this solution would be O((n-m)*m) as there are (n-m) substrings of size m and it will take O(m) time and space to check if they are anagrams or not. Here n and m are lengths of first and second string respectively.
 
 

We can also solve this problem by using std::is_permutation that determines if a sequence is a permutation of another sequence.

 
C++ implementation –
 

Download   Run Code

Output:

Anagram YZX present at index 2
Anagram XZY present at index 4
Anagram YZX present at index 6
Anagram XYZ present at index 9

 

Thanks for reading.




Please use ideone or C++ Shell or any other online compiler link to post code in comments.
Like us? Please spread the word and help us grow. Happy coding 🙂