Find All Anagrams in a String: definition
An anagram rearranges letters while preserving every letter count. This task finds all positions where a contiguous part of the text is an anagram of the pattern.
Task example: Find All Anagrams in a String
Given lowercase English strings s and p, return the zero-based starting indices of every substring of s with exactly the same letter counts as p. Matches may overlap. Return an empty list if none exist.
cba at index 0 and bac at index 6 both contain one a, one b, and one c. Keep searching after each match to collect every starting index.
Brute force: video explanation
s = "cbaebabacd", p = "abc" → [0, 6]
Prefer reading? Follow the steps below.
- Set m = len(p), count p once in need, and create result = []. Try every start with room for m letters.
- Build a fresh Counter for each candidate using indices. Compare all letter counts with need. If they match, append left to result.
- Record 0 for cba and 6 for bac. Continue after both matches, check the last candidate acd, then return [0, 6].
Time complexity · O(nm)
Let n = len(s) and m = len(p). For m ≤ n, counting p and rebuilding every candidate takes O(m + (n - m + 1)m), bounded by O(nm). If m > n, this version only counts p: O(m).
Space complexity · O(1) auxiliary + O(k) output
The frequency tables use O(1) auxiliary space for the fixed 26-letter alphabet. The returned list separately uses O(k) space for k matches. Total extra storage including the output is O(k + 1).
Sliding window: video explanation
s = "cbaebabacd", p = "abc" → [0, 6]
Prefer reading? Follow the steps below.
- If p is longer than s, return []. Otherwise count p, then scan s. Add the incoming character; once right ≥ m, subtract s[right - m].
- Compare only when right ≥ m - 1, so the window is complete. A match starts at right - m + 1; append that index and keep scanning.
- The windows cba and bac add 0 and 6. Overlaps are preserved: s = abab, p = ab returns [0, 1, 2]. Counter equality treats missing letters as zero counts in Python 3.10 and later.
Reusing the window avoids recounting m letters. Move one position at a time and keep every match. Unlike a Boolean existence check, this task cannot stop at the first match.
Time complexity · O(m + n)
Count p in O(m), then scan s once. Each update and comparison costs O(1) for 26 letters, so time is O(n + m). Appending k results is included because k ≤ n.
Space complexity · O(1) auxiliary + O(k) output
The frequency tables use O(1) auxiliary space for the fixed 26-letter alphabet. The returned list separately uses O(k) space for k matches. Total extra storage including the output is O(k + 1).