How to Solve the Anagram Indices Problem
word and a string
S, find all starting indices in
S which are anagrams of
For example, given that
word is “ab”, and S is “abxaba”, return 0, 3, and 4.
The brute force solution here would be to go over each word-sized window in S and check if they’re anagrams, like so:
from collections import Counter
This would take O(|W| * |S|) time. Can we make this any faster?
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:
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
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.
Ace your programming interview
Get a coding problem every day in your inbox!