Find All Anagrams in a String medium
Description
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 formed by rearranging the letters of another string, using all original letters exactly once.
Examples
> Case 1:
s = "cbaebabacd", p = "abc"
Output: [0, 6]
Explanation:
s[0..2] = "cba" is an anagram of "abc".
s[6..8] = "bac" is an anagram of "abc".
> Case 2:
s = "abab", p = "ab"
Output: [0, 1, 2]Constraints
1 <= s.length, p.length <= 3 * 10^4sandpconsist of lowercase English letters.
State design / Intuition
Two strings are anagrams if they have identical character frequency distributions. This is a fixed-size sliding window problem:
- Build a frequency count for
p. - Maintain a frequency count for the current window of size
m = len(p)ins. - When you slide the window right: decrement the count for the leaving character, increment for the arriving character.
- If the window count matches the pattern count, record the start index.
Comparing two 26-element arrays at each step is O(26) = O(1). Total time: O(n).
Optimization: instead of comparing two frequency arrays every step, maintain a matches counter that tracks how many of the 26 character frequencies are equal between the window and the pattern. Update matches on each window slide by checking only the two affected characters.
Code
Analysis
- Time: O(n + m) — O(m) to initialize frequency arrays, O(n) for the sliding window (each step is O(1) with the
matchescounter). - Space: O(1) — two 26-element arrays (constant size for lowercase ASCII).
Same skin
- Valid Anagram — same frequency comparison, no sliding window needed.
- Permutation in String (LC 567) — identical problem with
true/falseoutput instead of indices. - Minimum Window Substring — variable-length window version of the same frequency-tracking idea.
- Longest Substring with At Most K Distinct Characters — variable window with a HashMap instead of a fixed array.