Free lesson · DSA Mastery - Interview Prep, End to End

Find All Anagrams in a String

Medium7 min readdsasliding-window

Find All Anagrams in a String

Find All Anagrams in a String upgrades the fixed-size window from a running sum to a frequency map. You slide a window of width p.length() across s and report every start index where the window is an anagram of p - that is, where the window's character counts exactly match p's. We contrast the brute force (re-check every window's counts from scratch, O(n·k) or worse) against the sliding window that maintains counts incrementally and compares in O(1) using a match counter (O(n)).

The leap from the previous topic: the window's "state" is now a 26-entry count array instead of a single integer, and "is this window valid" means "do all 26 counts match the target."

The Problem

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 rearrangement of all the original letters exactly once.

Example 1:

Input:  s = "cbaebabacd", p = "abc"
Output: [0, 6]

Explanation:
  Substring at index 0 is "cba", an anagram of "abc".
  Substring at index 6 is "bac", an anagram of "abc".

Example 2:

Input:  s = "abab", p = "ab"
Output: [0, 1, 2]

Explanation: "ab" (0), "ba" (1), "ab" (2) are all anagrams of "ab".

Constraints:

• 1 <= s.length, p.length <= 3 * 10^4
• s and p consist of lowercase English letters.

Approaches Overview

Here k = p.length(). The window approach maintains a count array as it slides and tracks how many of the 26 letters currently have the correct count, so each step is O(1) instead of an O(k) recheck.

Approach 1: Brute Force

The Idea

For each window of width k in s, build its character counts (or sort it) and compare against p's counts. Record the start index on a match.

Logic Flowchart

graph TD
    A["pCount = counts of p"] --> B["For start i = 0 to n-k"]
    B --> C["winCount = counts of s[i..i+k-1]"]
    C --> D{"winCount == pCount?"}
    D -->|Yes| E["add i to result"]
    D -->|No| F["skip"]
    E --> G{"More i?"}
    F --> G
    G -->|Yes| B
    G -->|No| H["Return result"]

    style A fill:#4338ca,stroke:#6366f1,color:#f1f5f9
    style B fill:#4338ca,stroke:#6366f1,color:#f1f5f9
    style C fill:#b45309,stroke:#f59e0b,color:#f1f5f9
    style D fill:#b45309,stroke:#f59e0b,color:#f1f5f9
    style E fill:#16a34a,stroke:#10b981,color:#f1f5f9
    style F fill:#b45309,stroke:#f59e0b,color:#f1f5f9
    style G fill:#b45309,stroke:#f59e0b,color:#f1f5f9
    style H fill:#16a34a,stroke:#10b981,color:#f1f5f9

This flowchart shows the brute-force approach. We precompute the target's character counts, then for each window build its counts from scratch and compare. Rebuilding each window's counts makes the work the product of n and k.

Code

public static List<Integer> findAnagramsBrute(String s, String p) {
    List<Integer> result = new ArrayList<>();
    int n = s.length(), k = p.length();
    if (n < k) return result;

    int[] pCount = new int[26];
    for (char c : p.toCharArray()) pCount[c - 'a']++;

    for (int i = 0; i + k <= n; i++) {
        int[] win = new int[26];
        for (int j = i; j < i + k; j++) win[s.charAt(j) - 'a']++;
        if (Arrays.equals(win, pCount)) result.add(i);
    }
    return result;
}

This Java code counts the target's characters, then for each window rebuilds a 26-letter count array and compares it to the target. Rebuilding every window gives time proportional to n times k.

Complexity

Time: O(n·k) - each of ~n windows recounted in O(k). (The 26-entry compare is O(1).) Space: O(1) - fixed 26-entry arrays.

Adjacent windows share k-1 characters, so recounting each is wasteful. Maintaining the counts incrementally fixes it.

Approach 2: Sliding Window + Match Counter - Optimal

The Idea

Keep one count array for the window and slide it: when right enters, increment s[right]'s count; when left leaves (to keep width k), decrement s[left]'s count. To avoid an O(26) array compare each step, maintain a matches counter = how many of the 26 letters currently have window-count equal to target-count. When a count change makes a letter match, increment matches; when it breaks a match, decrement. The window is an anagram exactly when matches == 26.

Logic Flowchart

graph TD
    A["Build pCount; matches=0<br/>winCount all 0"] --> B["For right = 0 to n-1"]
    B --> C["add s[right]: update winCount<br/>and matches"]
    C --> D{"right >= k?"}
    D -->|Yes| E["remove s[right-k]: update<br/>winCount and matches"]
    D -->|No| F["window not full yet"]
    E --> G{"matches == 26?"}
    F --> G
    G -->|Yes| H["add (right-k+1) to result"]
    G -->|No| I["skip"]
    H --> J{"More?"}
    I --> J
    J -->|Yes| B
    J -->|No| K["Return result"]

    style A fill:#4338ca,stroke:#6366f1,color:#f1f5f9
    style B fill:#4338ca,stroke:#6366f1,color:#f1f5f9
    style C fill:#16a34a,stroke:#10b981,color:#f1f5f9
    style D fill:#b45309,stroke:#f59e0b,color:#f1f5f9
    style E fill:#dc2626,stroke:#ef4444,color:#f1f5f9
    style F fill:#4338ca,stroke:#6366f1,color:#f1f5f9
    style G fill:#b45309,stroke:#f59e0b,color:#f1f5f9
    style H fill:#16a34a,stroke:#10b981,color:#f1f5f9
    style I fill:#b45309,stroke:#f59e0b,color:#f1f5f9
    style J fill:#b45309,stroke:#f59e0b,color:#f1f5f9
    style K fill:#16a34a,stroke:#10b981,color:#f1f5f9

This flowchart shows the optimal approach. We maintain a window count array and a matches counter tracking how many of the 26 letters have the correct count. Adding a character on the right and removing one on the left each update the counts and the matches counter. When all 26 letters match, the window start index is recorded.

Code

public static List<Integer> findAnagrams(String s, String p) {
    List<Integer> result = new ArrayList<>();
    int n = s.length(), k = p.length();
    if (n < k) return result;

    int[] need = new int[26];
    for (char c : p.toCharArray()) need[c - 'a']++;

    int[] win = new int[26];
    int matches = 0;
    for (int i = 0; i < 26; i++) if (need[i] == 0) matches++;  // letters not needed start matched

    for (int right = 0; right < n; right++) {
        int in = s.charAt(right) - 'a';
        win[in]++;
        if (win[in] == need[in]) matches++;
        else if (win[in] == need[in] + 1) matches--;  // just broke a match

        if (right >= k) {
            int out = s.charAt(right - k) - 'a';
            win[out]--;
            if (win[out] == need[out]) matches++;
            else if (win[out] == need[out] - 1) matches--;  // just broke a match
        }

        if (matches == 26) result.add(right - k + 1);
    }
    return result;
}

// Usage:
// findAnagrams("cbaebabacd", "abc") -> [0, 6]
// findAnagrams("abab", "ab")        -> [0, 1, 2]

This Java code maintains a window count array and a matches counter initialized so letters not needed count as matched. Each entering character increments its count and updates matches; once the window is full, each leaving character decrements its count and updates matches. When all 26 letters match, the window's start index is recorded.

Step-by-Step Walkthrough

A frame-by-frame trace on s = "cbaebabacd", p = "abc" (k = 3, need = {a:1, b:1, c:1}). Each frame shows the window contents and whether all 26 match:

graph LR
    F0["right=2: window 'cba'<br/>a:1 b:1 c:1<br/>matches=26 ✓<br/>record 0"]
    F1["right=3..5: 'aeb','eba','bab'<br/>extra e / missing c<br/>no match"]
    F2["right=6: window 'bac'<br/>a:1 b:1 c:1<br/>matches=26 ✓<br/>record 6"]
    F3["right=7..9: 'acd' etc.<br/>missing b<br/>no match"]
    F0 --> F1 --> F2 --> F3

    style F0 fill:#16a34a,stroke:#10b981,color:#f1f5f9
    style F1 fill:#b45309,stroke:#f59e0b,color:#f1f5f9
    style F2 fill:#16a34a,stroke:#10b981,color:#f1f5f9
    style F3 fill:#b45309,stroke:#f59e0b,color:#f1f5f9

This walkthrough slides a width-three window across c b a e b a b a c d looking for anagrams of a b c. The window c b a at index zero matches, so zero is recorded. Windows containing an e or missing a c do not match. The window b a c at index six matches, so six is recorded.

Result: [0, 6].

Complexity

Time: O(n) - each character enters and leaves once, O(1) per step. Space: O(1) - fixed 26-entry arrays.

Complexity Comparison

The match counter is the key trick: it replaces an O(26) array comparison each step with O(1) bookkeeping, so the window stays truly linear. (Even comparing arrays directly each step is O(26·n) = O(n), but the counter generalizes cleanly to larger alphabets.)

Variations & Follow-ups

What if the alphabet were Unicode, not just lowercase?

Replace the 26-entry arrays with hash maps. The match-counter logic is identical; the compare-each-step alternative becomes O(alphabet) and less attractive.

What's the relationship to Permutation in String (next topic)?

Identical mechanics. "Is there an anagram of p in s" (Permutation in String) returns a boolean on the first match; "find all anagrams" collects every start index. Same window, different reporting.

What if you wanted anagram substrings of any length?

That's no longer fixed-size; you'd need a different formulation. Anagram matching inherently fixes the width at p.length().

What about edge cases?

• s shorter than p: No window fits; return empty.
• s equals p: One window, index 0, if it's an anagram.
• Repeated characters in p: Counts (not just presence) must match; the count array handles multiplicity.
• No anagrams: Return empty list.

Common Interview Pitfalls

• Comparing presence instead of counts. p = "aab" needs two a's; a window with one a and one b is not an anagram.
• Recording the wrong index. The start index when right is the last char is right - k + 1.
• Mis-initializing the match counter. Letters with need == 0 start as "matched"; forgetting this never reaches matches == 26.
• Updating matches incorrectly on remove. Removing a char can both break a match (count was equal) - handle the symmetric add/remove logic carefully.

Why This Problem Matters

Find All Anagrams generalizes the fixed-window technique from a scalar sum to a multiset (frequency) state, introducing the match-counter pattern for O(1) validity checks. This pattern - track how many sub-conditions are satisfied, update on each element's entry and exit - is the engine behind the hardest problem in this module, Minimum Window Substring (12.20), where it tracks how many required characters are covered.

The next topic, Permutation in String, is this exact technique returning a boolean instead of a list - and confirms how interchangeable "find all matches" and "does a match exist" are once the window is in place.

Back to DSA Mastery - Interview Prep, End to End