Every anagram
of a pattern

Anagram = same characters, same counts

Given a string S and a pattern P, find every starting index where a substring of S is an anagram of P. Order inside the window doesn't matter — abc, bca, and cab are all the same bag of letters. What matters is the frequency map: a→1, b→1, c→1.

For S = "aaba", P = "ab", the length-2 substrings are aa, ab, ba. Two match, so the answer is [1, 2] — and note they overlap at index 2.

Fixed length, heavy overlap → sliding window

Rebuilding a frequency table for every window is O(N·M); sorting each is O(N·M log M). Both re-derive almost-identical information. The fix is the same as the distinct-in-window problem: keep one frequency state and update only what changes.

Track the difference, and count what's off

Rather than keep two frequency tables and compare them, keep one difference table: diff[c] = pattern count − window count. Pattern characters add +1; window characters subtract 1. A window is an anagram exactly when every entry is zero — perfect cancellation.

The window, the diff table, the counter

Pick an S / P pair and step the window across. The diff table shows pattern − window per character — teal when an entry is zero, terracotta when it's off. The big number is nonZero; whenever it hits 0, the window (blue) turns solid and its start index is recorded.

Why outgoing is +1 and incoming is −1

Since diff = pattern − window, a character inside the window contributes −1. When it leaves, you undo that: −(−1) = +1. A character entering the window adds a fresh −1. So each slide is two updates:

Each update wraps in the same helper: before changing diff[c], if it was non-zero decrement nonZero; after changing it, if it's non-zero increment nonZero. That keeps the counter exact in O(1).

"aaba" against "ab"

Pattern diff seeds to a:+1, b:+1. Then the first window subtracts, and each slide swaps one char:

One diff array, one counter

import java.util.*;

static int update(int[] diff, int nonZero, char ch, int delta) {
    if (diff[ch] != 0) nonZero--;   // old contribution to mismatch
    diff[ch] += delta;
    if (diff[ch] != 0) nonZero++;   // new contribution
    return nonZero;
}

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

    int[] diff = new int[65536];   // every Java char, no alphabet assumption
    int nonZero = 0;

    for (int i = 0; i < m; i++) nonZero = update(diff, nonZero, p.charAt(i),  1);
    for (int i = 0; i < m; i++) nonZero = update(diff, nonZero, s.charAt(i), -1);
    if (nonZero == 0) res.add(0);

    for (int i = m; i < n; i++) {
        nonZero = update(diff, nonZero, s.charAt(i - m),  1);  // outgoing
        nonZero = update(diff, nonZero, s.charAt(i),     -1);  // incoming
        if (nonZero == 0) res.add(i - m + 1);
    }
    return res;
}

Using int[65536] covers every Java char without assuming lowercase-only input. If the problem guarantees a–z, use int[26] with ch − 'a' — even comparing all 26 entries per window is O(26N) = O(N).

Optimization is removing repeated work

• Generate every permutation of PO(M!)
• Sort & compare each windowO(N·M log M)
• Rebuild frequencies each windowO(N·M)
• Slide frequencies, compare full tableO(N·Σ)
• Slide + maintain mismatch counterO(N + M)

Each rung removes work the rung above repeats. The last step is the key leap: don't even re-compare information that didn't change — maintain a single number that already knows whether everything matches. O(N) is optimal since you must read every character at least once.

Same skeleton as distinct-in-window, richer state

The loop is identical to the distinct-elements problem — build the first window, record the answer, then repeatedly drop the outgoing and add the incoming. What changes is the state you maintain and how you read the answer from it:

Sliding window only tells you "one leaves, one enters." The craft is choosing a state whose answer updates in O(1) — here, a difference table paired with a mismatch counter.

Reconstruct it, don't memorize it

1. Anagram means the same character frequencies.
2. Same frequencies imply the same length → windows of size P.length().
3. Adjacent windows overlap heavily → slide, don't rebuild.
4. Keep diff = pattern − window; an anagram makes every entry zero.
5. Track nonZero so "all zero" is an O(1) check, not a full scan.
6. Each slide: undo outgoing (+1), add incoming (−1); if nonZero is 0, record i−M+1.