Given two strings s and p, return an array of all the start indices of p's anagrams in s. You may return the answer in any order.
An anagram is a string that contains the same characters, only the order of characters can be different.
Example 1:
Input:s = "cbaebabacd", p = "abc"
Output:[0, 6]
The substrings "cba" (index 0) and "bac" (index 6) are anagrams of "abc".
Example 2:
Input:s = "abab", p = "ab"
Output:[0, 1, 2]
Substrings "ab" (0), "ba" (1), "ab" (2) are all anagrams of "ab".
Constraints:
1 ≤ s.length, p.length ≤ 3 × 10⁴
s and p consist of lowercase English letters.
Hints
Hint 1How do you check if two strings are anagrams of each other?▼
Two strings are anagrams if their character frequency maps are equal. Use a hash map (Counter) to count each character, then compare the two maps.
Hint 2Checking every substring naively is O(n·m). Can you do better?▼
Use a fixed-size sliding window of length len(p). As you slide right, add the new character to sCount and remove the character that just left the window. Compare sCount to pCount in O(26) = O(1).
Hint 3What is the overall time complexity of the sliding window approach?▼
O(n) time: each character enters and exits the window exactly once. O(1) extra space: the frequency maps are bounded by 26 lowercase letters. Each comparison is O(26) = O(1).
🌐 Real-World Analogy
DNA Sequence Matching
In bioinformatics, researchers scan large genomic strings looking for all occurrences of a pattern sequence, regardless of base-pair order. This is exactly the anagram problem — does the current window of DNA contain all the same nucleotides as the target gene, just rearranged? The sliding window approach scans the entire genome in O(n), making it practical for sequences with billions of characters.
Optimal Approach — Fixed Sliding Window
O(n) Time
🪟
Fixed Window + Frequency Comparison
Time O(n)Space O(1)
Maintain a fixed window of size len(p). At each position, the window's character frequency map must equal pCount for an anagram to exist at that start index.
1Build pCount from p. Build sCount from the first len(p) characters of s.
2If sCount == pCount, add index 0 to results.
3Slide the window right: add s[i], remove s[i - len(p)] (clean up zero counts).
4If sCount == pCount, add the new start index to results.
5Return results after scanning all positions.
Because the alphabet is fixed (26 lowercase letters), comparing two frequency maps is O(1). The full scan is O(n) with O(1) extra space.
Discussion
…