A fraud rule treated a typed password as compromised if any contiguous slice was a rearrangement of a known PIN. The first version copied every slice of length m, sorted it, and compared to the sorted PIN. A dozen test logins returned instantly. A night of auth traffic was still allocating a char array per slice when the job was killed.

Permutation in String asks whether some contiguous window of s2 is an anagram of s1. Valid Anagram is that frequency test on one pair of whole strings. Restarting it on every slice uses that and still pays a factor of (n − m).

This is an interview writeup, not a sliding-window lecture. The sliding window post owns grow and shrink. Here we only care about a fixed window of length m = s1.length() whose letter counts we update by one character on each step.

The problem

Given strings s1 and s2, return true if s2 contains a permutation of s1 as a contiguous substring — any anagram of s1 appears as a window in s2 — and false otherwise. If s1 is longer than s2, return false. Assume lowercase English letters unless a follow-up widens the alphabet.

s1 = "ab",  s2 = "eidbaooo"  →  true    ("ba")
s1 = "ab",  s2 = "eidboaoo"  →  false
s1 = "abc", s2 = "ab"        →  false   s1 longer than s2

Note: Sort s1 once, then sort every window of length m, is a legal middle path. It is not the usual interview answer: you still permute (n − m + 1) slices. One pair of 26-slot counts answers in a pass.

An anagram check on every slice is the honest brute force

For every start i in s2 where a window of length m still fits, run a Valid Anagram check against s1. Correct. O((n − m) · m) with a count, worse if each slice sorts.

boolean checkInclusionNested(String s1, String s2) {
    int m = s1.length();
    int n = s2.length();
    if (m > n) {
        return false;
    }
    for (int i = 0; i <= n - m; i++) {
        if (isAnagram(s1, s2.substring(i, i + m))) {
            return true;
        }
    }
    return false;
}

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 night of auth lines you paid a nested Valid-Anagram for a question one slide answers in a pass: do the letter counts of this window of length m match s1?

Fixed length m: add the right character, drop the left

The window is always m characters. Count s1 into need[26]. Count the first m characters of s2 into window[26]. If the two arrays match, return true. Then walk right from m to n − 1: increment s2.charAt(right), decrement the character that just left (s2.charAt(right − m)). After each slide, compare again — Arrays.equals on the two 26-slot arrays, or a need/matches counter of how many letters still differ.

You never sort a slice. You never recount the whole window. Group Anagrams hashes signatures on a list of words; this is a haystack window, not a catalog bucket.

Walk "eidbaooo" with s1 = "ab":

s1 = ab                 need  a:1 b:1
s2 = e i d b a o o o
     0 1 2 3 4 5 6 7
m = 2

[0..1] ei   window e:1 i:1     vs need  miss
drop e, add d
[1..2] id   window i:1 d:1     vs need  miss
drop i, add b
[2..3] db   window d:1 b:1     vs need  miss
drop d, add a
[3..4] ba   window b:1 a:1     vs need  match → true

The Java is that walk with Arrays.equals after each slide:

boolean checkInclusion(String s1, String s2) {
    int m = s1.length();
    int n = s2.length();
    if (m > n) {
        return false;
    }
    int[] need = new int[26];
    int[] window = new int[26];
    for (int i = 0; i < m; i++) {
        need[s1.charAt(i) - 'a']++;
        window[s2.charAt(i) - 'a']++;
    }
    if (Arrays.equals(need, window)) {
        return true;
    }
    for (int right = m; right < n; right++) {
        window[s2.charAt(right) - 'a']++;
        window[s2.charAt(right - m) - 'a']--;
        if (Arrays.equals(need, window)) {
            return true;
        }
    }
    return false;
}

Time is O(n) — one pass over s2, a 26-slot compare per step. A matches counter that tracks how many of the 26 letters currently equal need drops the scan to O(1) per slide; the bill is still linear. Space is O(1) for the fixed alphabet. A map would pay extra space if the follow-up opens Unicode; that layout is the hash table post, not this board.

Note: The window length is always m. Growing until you have collected every letter of s1 accepts extra characters in the middle — that is a subsequence, not a permutation substring. Drop the character that just left; do not restart a Valid-Anagram sort.

What interviewers usually poke next

  • Find All Anagrams in a String. Same fixed window, same counts. Return every start index instead of a boolean.
  • matches / need instead of Arrays.equals. Count how many of the 26 letters currently differ. On add or drop, update that letter’s equality, then test matches == 26 (or need == 0). Same linear pass, no 26-slot scan.
  • Unicode, not just a–z. The 26-slot array is a lie. Use a map, same add/drop, unbounded keys.
  • Group Anagrams. Signatures on a list of words, not a haystack window. Do not solve it here.
  • Empty s1. Ask. An empty permutation sits at every index in some definitions; production constraints usually give m ≥ 1.

You are done with this problem when you can say, out loud, why a Valid-Anagram check on every slice is correct, why the window stays length m, and why adding one character and dropping one replaces a full recount.