Two strings are anagrams when one is a rearrangement of the other: the same letters, each used the same number of times, in any order. "post", "stop" and "spot" are all anagrams of each other.
Write find_anagrams(text: str, word: str) -> list[int]: every index i where the piece of text that starts at i and has the same length as word (text[i : i + len(word)]) is an anagram of word. Return the indices in increasing order, or [] if there are none.
Both strings contain only lowercase letters a-z.
find_anagrams("stopspot", "post") # [0, 1, 4]: "stop", "tops", "spot"
find_anagrams("tabbatbat", "tab") # [0, 3, 4, 5, 6]: "tab", "bat", "atb", "tba", "bat"
find_anagrams("aaaa", "aa") # [0, 1, 2]: the matches may overlap
find_anagrams("cat", "cats") # []: word is longer than text
Constraints: 1 <= len(text), len(word) <= 2 * 10^5.
⭐ Bonus: sorting or counting every piece from scratch still passes; a speed test with a 200,000-letter text and a 3,000-letter word earns a star in O(n) (O(26·n) is fine).
Show hint
neighbouring pieces share all but one letter at each end. Keep letter counts for the current piece and update them as it slides one step to the right.