Find All Anagrams in a String
01 · Problem
Given two strings s and p, find every position in s where a substring of length p.length begins that is an anagram of p — that is, it uses exactly the same letters as p with the same counts, in any order.
Return the starting indices of all such substrings in ascending order. If there are none (including when p is longer than s), return an empty array []. Overlapping matches are all reported.
02 · Examples
s = "dogxgodo", p = "god"
[0,4]
The window "dog" at index 0 and the window "god" at index 4 are anagrams of "god"; they do not overlap.
s = "mnmnm", p = "nm"
[0,1,2,3]
Every window of length 2 ("mn", "nm", "mn", "nm") is an anagram of "nm"; overlapping matches count.
s = "hello", p = "xyz"
[]
No window of s contains the letters x, y and z, so the result is empty.
03 · Constraints
- 011 <= s.length, p.length <= 3 * 104
- 02s and p consist of lowercase English letters
- 03Indices in the output must be in increasing order
04 · Optimal complexity
- Time
- O(n)
- Space
- O(1)
Practice it alone or rehearse it as an interview.
Practice Mode gives you an editor and test runs, nothing else. AI Interview Mode puts a voice interviewer on the other side, adds a clock, and ends with a scored summary of the round.