Find All Anagrams in a String

mediumAmazon-tagged: Arrays & Strings71 stepsJava · Python · C++

Return every start index where a window of s is an anagram of p. Slide a window of length |p| and keep letter counts; compare the window's counts with p's counts after each slide.

▶ Watch the animated trace

Traced input: s = "cbaebabacd", p = "abc" → [0, 6]. Original problem: leetcode.com/problems/find-all-anagrams-in-a-string/

Complexity

BestO(n)

AverageO(26·n)

WorstO(26·n)

SpaceO(1)

Comparing two 26-count arrays per slide; a match counter makes it O(n).

Key idea

Anagram = same letter counts.
Add the entering letter, remove the leaving letter.
Record the window's start whenever the counts match.

Common mistakes

Rebuilding counts for each window is O(n·m).
Off-by-one on when to start removing the left letter.

Solution

Java

List<Integer> findAnagrams(String s, String p) {
    List<Integer> res = new ArrayList<>();
    if (p.length() > s.length()) return res;
    int[] need = new int[26], win = new int[26];
    for (char c : p.toCharArray()) need[c - 'a']++;
    for (int i = 0; i < s.length(); i++) {
        win[s.charAt(i) - 'a']++;
        if (i >= p.length()) win[s.charAt(i - p.length()) - 'a']--;
        int start = i - p.length() + 1;
        if (start >= 0 && Arrays.equals(win, need)) res.add(start);
    }
    return res;
}

Python

def findAnagrams(s: str, p: str) -> List[int]:
    res = []
    if len(p) > len(s): return res
    need, win = Counter(p), Counter()
    for i, c in enumerate(s):
        win[c] += 1
        if i >= len(p):
            old = s[i - len(p)]
            win[old] -= 1
            if win[old] == 0: del win[old]
        if i >= len(p) - 1 and win == need: res.append(i - len(p) + 1)
    return res

C++

vector<int> findAnagrams(string s, string p) {
    vector<int> res;
    if (p.size() > s.size()) return res;
    array<int, 26> need{}, win{};
    for (char c : p) need[c - 'a']++;
    for (int i = 0; i < (int)s.size(); i++) {
        win[s[i] - 'a']++;
        if (i >= (int)p.size()) win[s[i - p.size()] - 'a']--;
        int start = i - (int)p.size() + 1;
        if (start >= 0 && win == need) res.push_back(start);
    }
    return res;
}

Edge cases

Each one has its own trace in the interactive view.

Case	Input	Answer
Overlapping matches Every window of length 2 works.	`s = "abab", p = "ab"`	`[0, 1, 2]`
p longer than s No full window fits.	`s = "a", p = "ab"`	`[]`
Repeated letters Counts must match exactly.	`s = "aaab", p = "aa"`	`[0, 1]`