c++ - Given a word and a text, we need to return the occurrences of anagrams

Question

Given a word and a text, return the count of the occurrences of anagrams of the word in the text. For eg. word is “for” and the text is “forxxorfxdofr”, anagrams of “for” will be “ofr”, “orf”,”fro”, etc. So the answer would be 3 for this particular example.

I have got the brute force approach which is getting all the permutations of the word, then compare if the text contains it, and increase the number of occurrences, but that is O(N^2) approach. I'm looking for a better complexity.

Answer 1

You can simply look for the character count.

Say for example that you're looking for anagramms of look. So, you're looking for:

• a 4 charachter length word,
• with 1 l, 2 o and 1 k.

Simply process the first 4 letters, store the counts. Check whether you have a match. Add the next character (increment), remove the old character (decrement). Check again. And so on...