A fraud rule asked for every offset in a request path where a window was a jumble of a known token — abc hiding as cba or bac. The first version sliced every stretch of length p and ran Valid Anagram. A 40-character path returned before the page rendered. A day’s access log was still recounting each slice when the rule timed out.

Find every start index where a window of s of length p is an anagram of p. Valid Anagram is that frequency test on one pair. Nested checks use it and still pay a recount per start.

This is an interview writeup, not a sliding-window lecture. The sliding window post owns grow and shrink. The hash table post owns buckets. Here we only care about a fixed window of length p: slide one character, and collect the left index whenever the counts match. Do not restart. Do not stop at the first hit.

The problem

Given strings s (haystack) and p (pattern), return every start index i such that the window s[i .. i + p.length() - 1] is an anagram of p. Indexes should increase. If p is longer than s, or either side is empty, return an empty list. Assume lowercase English letters unless a follow-up widens the alphabet.

s = "cbaebabacd", p = "abc"  →  [0, 6]   windows "cba", "bac"
s = "abab",       p = "ab"   →  [0, 1, 2]
s = "ab",         p = "abc"  →  []       p longer than s
s = "",           p = "a"    →  []

Note: Group Anagrams buckets a list of words by signature. This prompt slides one haystack. Permutation in String is the same window with a boolean: first match is enough. Here you keep walking and collect every start.

Nested Valid Anagram is the honest brute force

For every start i that still has room for p, take the slice and run Valid Anagram (sort both, or count 26 letters). Correct. Quadratic in the haystack times the pattern cost, and substring allocates a new copy each time.

List<Integer> findAnagramsNested(String s, String p) {
    List<Integer> starts = new ArrayList<>();
    int n = s.length();
    int m = p.length();
    for (int i = 0; i + m <= n; i++) {
        if (isAnagram(s.substring(i, i + m), p)) {
            starts.add(i);
        }
    }
    return starts;
}

boolean isAnagram(String a, String b) {
    char[] ca = a.toCharArray();
    char[] cb = b.toCharArray();
    Arrays.sort(ca);
    Arrays.sort(cb);
    return Arrays.equals(ca, cb);
}

At n = 20 this is a rounding error. At a day’s access log you paid a recount per start for a question one window answers in a pass: same length, same counts — record the left index and slide one.

Fixed window: add right, drop left, collect every start

p.length() never changes, so the window size is fixed. Build a 26-slot need from p. Maintain have for the current window of s. Fill the first m characters; if have equals need, record 0. Then, for each new right end, increment s.charAt(right) and decrement the character that just left (s.charAt(right - m)). If the arrays match, record right - m + 1.

You never rebuild have from scratch. You never return on the first hit. Walk "cbaebabacd" against "abc":

s = c b a e b a b a c d
    0 1 2 3 4 5 6 7 8 9
p = abc   m = 3   need {a:1, b:1, c:1}

[0..2] cba   {a:1,b:1,c:1}  match → 0
drop c add e  bae   {a:1,b:1,e:1}  no
drop b add b  aeb   {a:1,b:1,e:1}  no
drop a add a  eba   {a:1,b:1,e:1}  no
drop e add b  bab   {a:1,b:2}      no
drop b add a  aba   {a:2,b:1}      no
drop a add c  bac   {a:1,b:1,c:1}  match → 6
drop b add d  acd   {a:1,c:1,d:1}  no

The Java is that walk. Arrays.equals on 26 slots is a constant alphabet scan — the same check Valid Anagram already used on a pair. Overlapping hits ("abab" / "ab" → [0, 1, 2]) fall out of sliding by one; jumping a full m would miss them.

List<Integer> findAnagrams(String s, String p) {
    List<Integer> starts = new ArrayList<>();
    int n = s.length();
    int m = p.length();
    if (m == 0 || m > n) {
        return starts;
    }

    int[] need = new int[26];
    int[] have = new int[26];
    for (int i = 0; i < m; i++) {
        need[p.charAt(i) - 'a']++;
        have[s.charAt(i) - 'a']++;
    }
    if (Arrays.equals(need, have)) {
        starts.add(0);
    }

    for (int right = m; right < n; right++) {
        have[s.charAt(right) - 'a']++;
        have[s.charAt(right - m) - 'a']--;
        if (Arrays.equals(need, have)) {
            starts.add(right - m + 1);
        }
    }
    return starts;
}

Time is O(n) — one pass over s, plus a 26-slot compare per window. Space is O(1) for the two count arrays, plus the output list. A map is the same idea when the alphabet is not 26 letters.

Note: Do not return when the first window matches. Permutation in String may stop there. This prompt wants every start. Sliding off a match (0 in the trace) and later hitting 6 is the point, not a bug.

What interviewers usually poke next

  • Permutation in String. Same fixed window and counts. Boolean vs a list of starts. If you already collect, a nonempty list is the boolean.
  • Matches counter vs Arrays.equals. Track how many of the 26 letters currently equal need, and update only the character that entered and the one that left. Still O(n), fewer slot scans. Same answers.
  • Unicode / mixed case. The 26-slot array is then the wrong alphabet. Ask the range; count in a map of code points, same slide.
  • Group Anagrams. Many strings, one signature each, buckets. Not a window over one haystack.
  • Return the slices. You already have i and m; s.substring(i, i + m) is a follow-up, not this return type.

You are done with this problem when you can say, out loud, why a Valid Anagram on every slice is correct, why a fixed window of length p is enough, and why the first match is not the whole answer.