Find every anagram window of a pattern

Question

Given a text and a shorter pattern, find every start index in the text where a window of the pattern's length is an anagram of the pattern, the same characters with the same multiplicities, in any order.

text = "cbaebabacd", pattern = "abc"
-> [0, 6]          # "cba" and "bac" are anagrams of "abc"

Return all such start indices. Aim for $O(n)$ .

Accepted Answer

Let k be the pattern length. Build the pattern's character-count map. Slide a fixed-size window of length k over the text, maintaining its own count map: add the entering character, and once the window exceeds k, remove the leaving character (deleting zero-count keys). Whenever the window's map equals the pattern's map, record the window's start index. Tracing text = "cbaebabacd", pattern = "abc": the window matches at index 0 ("cba") and index 6 ("bac"), giving [0, 6]. Time O(n), each step does O(1) map updates, and the dictionary equality compares at most 26 keys for lowercase letters (a co…

Find every anagram window of a pattern

Your answer

More Coding questions