Back to solutions

Find All Anagrams in a String

MediumArrays

Return start indices of all anagrams of p within s.

Open problem
Constraints
  • 1 <= |s|, |p| <= 3*10^4
  • lowercase English letters

Sliding window of counts

Time O(|s|)Space O(1) (26 letters)

Anagrams share the same letter counts. Keep a frequency array for p and a sliding window of the same length over s. Slide one character at a time, adding the new character and removing the one that left. Whenever the window's counts match p's counts, record the start index.

Key terms
anagram:
A rearrangement of the same multiset of characters.
fixed-size sliding window:
A window of constant length |p| that advances across s.
vector<int> findAnagrams(const string& s, const string& p) {
    vector<int> res; if (s.size() < p.size()) return res;
    int need[26] = {0}, win[26] = {0};
    for (char c : p) need[c - 'a']++;
    int k = p.size();
    for (int i = 0; i < (int)s.size(); i++) {
        win[s[i] - 'a']++;
        if (i >= k) win[s[i - k] - 'a']--;
        if (i >= k - 1 && equal(begin(need), end(need), begin(win)))
            res.push_back(i - k + 1);
    }
    return res;
}
Step by step
  1. Build the target letter counts for p.
  2. Maintain a window of length |p| over s, updating counts as it slides.
  3. When the window's counts equal the target, the window start is an anagram index.
  4. Collect all such start indices.