Given a word and a string S, find all starting indices in S which are anagrams of word.

For example, given that word is “ab”, and S is “abxaba”, return 0, 3, and 4.

### Brute force

The brute force solution here would be to go over each word-sized window in S and check if they’re anagrams, like so:

This would take O(|W| * |S|) time. Can we make this any faster?

### Rolling hash

One way to solve this problem is to use the Rabin-Karp algorithm. The basic idea is that we could make a frequency-based hash of the target word and check if any window under s hashes to the same value. That is, the hash would be the sum of char * prime_num ** char_freq for each character and their frequency. If the hash of the word and window matches, we could do a manual == of the two strings. Since collisions are expected to be rare, this would be O(S). However, there’s an easier way to solve this problem:

### Count difference

Notice that moving along the window seems to mean recomputing the frequency counts of the entire window, when only a little bit of it actually updated. This insight leads us to the following strategy:

• Make a frequency dictionary of the target word
• Continuously diff against it as we go along the string
• When the dict is empty, the window and the word matches

We diff in our frequency dict by incrementing the new character in the window and removing
old one.

This should run in O(S) time.

Are you interviewing for programming jobs, or do you just enjoy fun programming questions? Check out our newsletter, Daily Coding Problem, to get a question in your inbox every day.