MediumPythonJavaScriptTypeScript
Strings — Find All Anagrams in a String
AlgorithmsStringsSliding WindowHash Map
solve(s, p) — s and p contain lowercase letters. Return the start indices, in
increasing order, of every substring of s that is an anagram of p (the same letters
with the same counts, in any order).
Slide a window of length p.length over s and keep 26 letter counts for it. Moving the
window one step adds one letter and removes one, so you update the counts in O(1) and compare
them with p's counts — O(26 · n) overall, no sorting of substrings.
Examples
solve("cbaebabacd", "abc") → [0,6]
solve("abab", "ab") → [0,1,2]
solve("a", "ab") → []Sample tests
Test #1Two anagrams
Input: ["cbaebabacd","abc"]
Output: [0,6]
Test #2Overlapping anagrams
Input: ["abab","ab"]
Output: [0,1,2]
Test #3Pattern longer than the text
Input: ["a","ab"]
Output: []