Iteration
Count Anagrams
Given a string s and a shorter string t, return the total number of substrings in s that are anagrams of t.
Example:
Explanation: There are 3 substrings that are anagrams of the word "ab". The first is "ba", the second is "ab", and the third is another "ba".
Two strings are anagrams if the count of each of their letters is the same. For example, all of these words are anagrams, because the count of each letter is the same:
To solve this problem, you can slide a window of size len(t) across the string, and compute the count of each letter in the window.
To do this efficiently, when you slide the window, you should add the 1 new letter, and remove 1 old letter, like this:
Here's how you code this up:
Time Complexity O(n). We loop over every possible window, which is O(n) iterations where n is the size of the string s. In each iteration, we check whether tCount and windowCount are the same, which takes worst-case 26 operations. This gives O(26*n) = O(n) total operations.
Space Complexity O(1). Each HashMap stores the letters a-z, which is O(26) elements. We also store the solution as an integer. This gives a total of O(26+26+1) = O(1) total space.
There's a minor optimization you can make to this code so that it takes O(n) time, instead of O(26*n) time. See below for details.
The factor of 26 comes from the 26 operations that it takes to run windowCount == tCount. A HashMap might have 26 keys that need to be compared with the other HashMap.
To avoid this O(26) comparison, you can instead keep track of the number of letters that each HashMap has in common numincommon and and compare these instead. That's just 1 single comparison, not 26.
Here's how you code this up:
Time Complexity O(n). Building the HashMaps takes O(n) time. Looping over each window takes O(n) time. Adding these up gives O(n).
Space Complexity O(1). We store each HashMap and 2 integers, giving O(26+26+1+1) = O(1) space.
