Loading…

mediumStringsLC #567Frequently asked

Permutation in String

Q: How do you solve Permutation in String using the Brute Force — Recount Every Window approach?

When to use it: Say it first to anchor the baseline and to make 'permutation = equal counts' explicit. Build the frequency count of `s1`. Then for every start index `i` in `s2` such that a length-|s1| window fits, count the characters of `s2[i .. i+|s1|-1]` and compare to `s1`'s counts. Return true on the first window whose counts match. **Why this is the natural first attempt.** It hinges on the key realization: a permutation is exactly an equal-length, equal-frequency match. Once you see that, comparing counts per window is the obvious correct method (sorting each window and comparing strings is an equivalent, slightly slower variant). **Why we don't ship this.** Recounting each window from scratch ignores that consecutive windows overlap in all but two characters. With |s1| and |s2| up to 10⁴, the O(|s2|·|s1|) product is wasteful. Sliding the window and updating only the entering and leaving character makes each step O(1). Time complexity: O(|s2| · |s1|). Space complexity: O(1).

Q: How do you solve Permutation in String using the Fixed-Size Sliding Window of Counts (Optimal) approach?

When to use it: The answer they want. Phrase it as 'slide a window of length |s1|, adding the entering char and removing the leaving one, comparing counts'. Because every permutation of `s1` has length `|s1|`, the window size is fixed — we only ever look at length-`|s1|` slices of `s2`. Build `need` (s1's counts) and `window` (counts of the first `|s1|` characters of `s2`), then slide. **Sliding in O(1) per step.** Moving the window one position right means exactly two changes: the new character at index `i` enters (increment its count) and the character at index `i − |s1|` leaves (decrement its count). The window's length is preserved automatically by always pairing one add with one remove. No recounting. **Checking the match cheaply with a `matches` counter.** Comparing the two 26-length arrays every slide is O(26) — fine, and still O(|s2|) overall, but we can do strict O(1) per step. Keep `matches` = the number of letters `x` for which `window[x] == need[x]`. When we change a letter's window count, we look at whether that letter's equality flipped: if it was equal and now isn't, `matches--`; if it just became equal, `matches++`. The window is a permutation of `s1` exactly when `matches == 26`. **Why equal counts is the whole test.** Two strings are permutations of each other iff they have identical character frequencies. Length equality is guaranteed by the fixed window, so frequency equality is both necessary and sufficient — no need to consider order at all. **Why the early exit matters.** If `|s1| > |s2|`, no window fits and the answer is immediately false; this also prevents constructing an out-of-range initial window. **Why O(|s2|) time and O(1) space.** Each character of `s2` enters and leaves the window at most once, and the only storage is two constant-size count arrays plus the matches counter. Time complexity: O(|s2|). Space complexity: O(1).

LCPractice

Sliding Window · 5 of 6 · 9 min

Given two strings s1 and s2, return true if s2 contains a permutation of s1, or false otherwise.

In other words, return true if one of s1's permutations is a substring of s2.

In plain English

A permutation of s1 is any reordering of its characters, so it has exactly s1's length and exactly s1's character frequencies. The task reduces to: does any length-|s1| substring of s2 have the same character counts as s1? That's a fixed-size window scan.

Examples

Example 1

Input: s1 = "ab", s2 = "eidbaooo"
Output: true
Note: s2 contains "ba" at indices 3–4, which is a permutation of "ab".

Example 2

Input: s1 = "ab", s2 = "eidboaoo"
Output: false
Note: No length-2 window of s2 has counts {a:1, b:1}.

Example 3

Input: s1 = "adc", s2 = "dcda"
Output: true
Note: "dca" (indices 1–3) is a permutation of "adc".

Constraints

1 ≤ s1.length, s2.length ≤ 10⁴
s1 and s2 consist of lowercase English letters

Clarifying questions4First question: Does the permutation have to be contiguous in s2?Explore questions

Q1.Does the permutation have to be contiguous in s2?
Yes — it must appear as a substring (a contiguous block), not a scattered subsequence.
Q2.What defines a permutation match?
Same length and identical character frequencies as s1; order doesn't matter.
Q3.What if s1 is longer than s2?
No window of length |s1| fits in s2, so return false immediately.
Q4.What's the alphabet?
Lowercase English letters — a fixed 26-slot count array, so space is O(1).

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

Return true if s2 contains a substring that is a permutation (anagram) of s1. Since any permutation of s1 has the same length and character counts, slide a fixed-size window of length |s1| across s2 and check whether the window's character counts match s1's. Maintain the counts incrementally with a 'matches' counter. O(|s2|) time, O(1) space (26 counts).

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Whether you recognize that a permutation is just an equal-multiset, equal-length match, and use a fixed-size sliding window of counts updated incrementally rather than re-sorting or recounting each window.

Where candidates slip

Re-sorting or rebuilding the count map for every window (O(|s1|) per slide), or forgetting the add-and-remove pairing so the window drifts off its fixed size.

How to stand out

State the sort-each-window brute force, then 'counts must match and lengths are equal, so a fixed window of frequencies sliding in O(1) per step works'. Mention the matches counter for strict O(|s2|).

Choose

Compare the available approaches

Use constraints and trade-offs to select the route you can defend in an interview.

Approaches at a glanceCompare before you dive in

#	Approach	Time	Space	When to mention	Jump
1	Brute Force — Recount Every Window	`O(\|s2\| · \|s1\|)`	`O(1)`	Say it first to anchor the baseline and to make 'permutation = equal counts' explicit.	Read
2	Fixed-Size Sliding Window of Counts (Optimal)Optimal	`O(\|s2\|)`	`O(1)`	The answer they want. Phrase it as 'slide a window of length \|s1\|, adding the entering char and removing the leaving one, comparing counts'.	Read

Interactive decision treeInteractiveChoose the right approachFollow the branches and learn why each constraint changes the solution.First decision previewDoes s2 contain a permutation of s1?Is the window size fixed?Yes (= |s1|)Yes + incrementalExplore the full tree

Learn & trace

Build each solution step by step

Move from the core idea to a visual trace, implementation, proof, and edge cases.

03.1

Approach 1 of 2

Brute Force — Recount Every Window

TimeO(|s2| · |s1|)SpaceO(1)

Say it first to anchor the baseline and to make 'permutation = equal counts' explicit.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

A permutation of s1 has the same length as s1. So only substrings of s2 of length |s1| can match.

2Hint 2Explore hint

For each such window, count its characters (or sort it) and compare to s1's counts (or sorted s1).

3Hint 3Explore hint

Scan all windows and return true on the first match. Each window recount is O(|s1|) — that's the inefficiency to remove.

A · Core idea

Build the frequency count of s1. Then for every start index i in s2 such that a length-|s1| window fits, count the characters of s2[i .. i+|s1|-1] and compare to s1's counts. Return true on the first window whose counts match.

Why this is the natural first attempt. It hinges on the key realization: a permutation is exactly an equal-length, equal-frequency match. Once you see that, comparing counts per window is the obvious correct method (sorting each window and comparing strings is an equivalent, slightly slower variant).

Why we don't ship this. Recounting each window from scratch ignores that consecutive windows overlap in all but two characters. With |s1| and |s2| up to 10⁴, the O(|s2|·|s1|) product is wasteful. Sliding the window and updating only the entering and leaving character makes each step O(1).

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

s1 = "ab", s2 = "eidba"

"ei"

{e:1,i:1} ≠ need

Stateno

Final resulttrue

C · Code with teaching comments

Reference implementation previewpublic boolean checkInclusion(String s1, String s2) { int len = s1.length(); if (len > s2.length()) return false; int[] need = new int[26]; for (char c : s1.toCharArray()) need[c - 'a']++;Explore the full code

solution.javaJava

Brute Force — Recount Every Window — reference

3 teaching notes

1
public boolean checkInclusion(String s1, String s2) {
2
    int len = s1.length();
3
    // No window of length |s1| fits — early exit.
4
    if (len > s2.length()) return false;
5
    int[] need = new int[26];
6
    for (char c : s1.toCharArray()) need[c - 'a']++;
7
    for (int i = 0; i + len <= s2.length(); i++) {
8
        int[] win = new int[26];
9
        // Recount the whole window — the O(|s1|) per-step waste.
10
        for (int j = i; j < i + len; j++) win[s2.charAt(j) - 'a']++;
11
        // Matching counts means this window is a permutation of s1.
12
        if (Arrays.equals(win, need)) return true;
13
    }
14
    return false;
15
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.15 lines

D · Why it works and complexityO(|s2| · |s1|) timeO(1) spaceOpen the invariant and proofExplore the proof

Adjacent windows differ by exactly one character added on the right and one dropped on the left. Recounting the whole window throws that away; incremental count maintenance is the entire optimization.

ComplexityO(|s2| · |s1|) time, O(1) space — There are O(|s2|) windows; counting each from scratch is O(|s1|), giving O(|s2|·|s1|). The count arrays are fixed 26 ints → O(1) space.

E · Edge cases and pitfalls3Recounting each window instead of sliding — the O(|s1|) per-step cost.Explore edge cases

Pitfalls

Recounting each window instead of sliding — the O(|s1|) per-step cost.
Comparing as sorted strings repeatedly, which is even slower (O(|s1| log |s1|) per window).
Missing the |s1| > |s2| early exit, risking out-of-range windows.

03.2

Approach 2 of 2 · Optimal

Fixed-Size Sliding Window of Counts (Optimal)

TimeO(|s2|)SpaceO(1)

The answer they want. Phrase it as 'slide a window of length |s1|, adding the entering char and removing the leaving one, comparing counts'.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Both the target length (|s1|) and the comparison (equal counts) are fixed. Build s1's count array and an initial window of the first |s1| chars of s2.

2Hint 2Explore hint

Slide the window one step at a time: add the new right character's count and subtract the character that exits on the left. The window size stays |s1|.

3Hint 3Explore hint

To avoid re-comparing all 26 counts each slide, track a `matches` counter of how many of the 26 letters currently have equal counts in window and need; the window is a permutation when matches == 26.

A · Core idea

Because every permutation of s1 has length |s1|, the window size is fixed — we only ever look at length-|s1| slices of s2. Build need (s1's counts) and window (counts of the first |s1| characters of s2), then slide.

Sliding in O(1) per step. Moving the window one position right means exactly two changes: the new character at index i enters (increment its count) and the character at index i − |s1| leaves (decrement its count). The window's length is preserved automatically by always pairing one add with one remove. No recounting.

Checking the match cheaply with a `matches` counter. Comparing the two 26-length arrays every slide is O(26) — fine, and still O(|s2|) overall, but we can do strict O(1) per step. Keep matches = the number of letters x for which window[x] == need[x]. When we change a letter's window count, we look at whether that letter's equality flipped: if it was equal and now isn't, matches--; if it just became equal, matches++. The window is a permutation of s1 exactly when matches == 26.

Why equal counts is the whole test. Two strings are permutations of each other iff they have identical character frequencies. Length equality is guaranteed by the fixed window, so frequency equality is both necessary and sufficient — no need to consider order at all.

Why the early exit matters. If |s1| > |s2|, no window fits and the answer is immediately false; this also prevents constructing an out-of-range initial window.

Why O(|s2|) time and O(1) space. Each character of s2 enters and leaves the window at most once, and the only storage is two constant-size count arrays plus the matches counter.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

s1 = "ab", s2 = "eidbaooo"

Array state

i=0..1

window "ei" — counts ≠ need

l ↓

[0]

r ↓

[1]

[2]

[3]

[4]

[5]

[6]

[7]

Current pointerResolved stateNot processed

Final resulttrue

C · Code with teaching comments

solution.javaJava

Fixed-Size Sliding Window of Counts (Optimal) — optimal

5 teaching notes

1
public boolean checkInclusion(String s1, String s2) {
2
    int len = s1.length();
3
    if (len > s2.length()) return false;
4
    int[] need = new int[26];
5
    int[] window = new int[26];
6
    for (int i = 0; i < len; i++) {
7
        need[s1.charAt(i) - 'a']++;
8
        window[s2.charAt(i) - 'a']++;
9
    }
10
    int matches = 0;
11
    for (int x = 0; x < 26; x++) {
12
        // Initialize matches = number of letters whose counts already agree.
13
        if (window[x] == need[x]) matches++;
14
    }
15
    for (int i = len; i < s2.length(); i++) {
16
        if (matches == 26) return true;
17
        int in = s2.charAt(i) - 'a';
18
        int out = s2.charAt(i - len) - 'a';
19
        window[in]++;
20
        if (window[in] == need[in]) matches++;
21
        // Overshot the target → that letter no longer matches.
22
        else if (window[in] == need[in] + 1) matches--;
23
        window[out]--;
24
        if (window[out] == need[out]) matches++;
25
        else if (window[out] == need[out] - 1) matches--;
26
    }
27
    // All 26 letters agree → the final window is a permutation of s1.
28
    return matches == 26;
29
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.29 lines

D · Why it works and complexityO(|s2|) timeO(1) spaceOpen the invariant and proofExplore the proof

Fixing the window size collapses the problem to 'do these two frequency vectors match as the window slides?'. The add-one/remove-one update keeps each step O(1), and the matches counter turns the 26-way comparison into a single integer test — the same incremental-equality trick that solves Find All Anagrams.

ComplexityO(|s2|) time, O(1) space — Building the counts is O(|s1|). Sliding across s2 is O(|s2|) steps, each O(1) with the matches counter (or O(26) with array compare, still O(|s2|)). The two 26-slot arrays are O(1) space.

E · Edge cases and pitfalls6s1 = "a", s2 = "a" — Window of size 1 equals need immediately → returns true before any slide.Explore edge cases

Edge cases handled

s1 = "a", s2 = "a"Window of size 1 equals need immediately → returns true before any slide.
s1 = "ab", s2 = "a"|s1| > |s2| → early return false.
s1 = "abc", s2 = "ccccbbbbaaaa"No length-3 window mixes a,b,c equally → returns false.

Pitfalls

Forgetting to check matches/equality for the initial window before sliding (missing a match at index 0).
Updating matches with wrong threshold logic (the need[x] ± 1 boundary conditions).
Not pairing every add with a remove, letting the window size drift away from |s1|.

Practice

Try the solution yourself

Edit the optimal implementation, test another input, and observe the result.

Editable code previewpublic boolean checkInclusion(String s1, String s2) { int len = s1.length(); if (len > s2.length()) return false; int[] need = new int[26]; int[] window = new int[26];Explore the playground

Try it — Java· run a complete program; method snippets need a driver

Avoid mistakes

Recognize the interview traps

Understand why common attempts fail before reviewing the corrected implementation.

Rebuilding the window each step

Adjacent windows overlap in all but two characters; recounting from scratch is O(|s1|) per step and defeats the point of a sliding window.

Explore the code comparison

Don't write this

for i in range(len(s2) - length + 1):
    win = [0] * 26
    for j in range(i, i + length):
        win[ord(s2[j]) - ord('a')] += 1

Write this instead

window[ord(s2[i]) - ord('a')] += 1
window[ord(s2[i - length]) - ord('a')] -= 1

Comparing strings instead of counts

A permutation is defined by equal frequencies, not order. Sorting each window to compare is correct but slower than count comparison.

Explore the code comparison

Don't write this

char[] a = window.toCharArray();
Arrays.sort(a);
if (new String(a).equals(sortedS1)) return true;

Write this instead

if (Arrays.equals(window, need)) return true;

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Fixed-size sliding window of frequency counts

Code pattern to memorize

if len(s1) > len(s2): return False
need, win = [0]*26, [0]*26
for c in s1: need[c]++ 
for i in range(len(s1)): win[s2[i]]++
if win == need: return True
for i in range(len(s1), len(s2)):
    win[s2[i]] += 1
    win[s2[i-len(s1)]] -= 1
    if win == need: return True
return False

Rules to remember

1A permutation has the same length and same character counts — order is irrelevant.
2The window is fixed-size at |s1|; slide by adding the new char and removing the one that falls off.
3Compare counts, not strings — a 26-length count array comparison is O(1).
4Early-exit false if |s1| > |s2| (no window can fit).
5A matches/required counter avoids re-comparing all 26 slots each slide for true O(|s2|).

Use this pattern when

Detect an anagram/permutation as a contiguous substring
The target window size is known and fixed
Equality of multisets can be tracked incrementally as the window slides
Fixed-length 'does this pattern appear (reordered)' substring problems

Choose another pattern when

Window size varies with a constraint → variable sliding window (LC3, LC76)
t must appear in order → substring search (KMP), not anagram matching
Need all matching positions → same window, collect indices (LC438)

Interview takeaway

When the target length is fixed, a fixed-size sliding window of character counts answers anagram-presence in one pass. Add-one / remove-one count maintenance plus a matches counter is the template — it extends directly to Find All Anagrams.

Continue

Transfer the pattern to another problem

Use a direct variation or pattern sibling to prove the idea is reusable.

Transferable patternFixed-size sliding window of frequency counts with incremental add/remove and a matches counter. Reach for it on anagram/permutation-presence problems where the window length is known. Same family as Find All Anagrams and Valid Anagram.

Practice queueDirect variations and pattern siblings

Direct follow-ups

Find All Anagrams in a String
Coming soon
Same fixed-size window, but collect every start index where counts match instead of returning on the first.
Minimum Window Substring
Variable window that must cover (not equal) t — grow then shrink.
Valid Anagram
The count-equality test without the window — just compare frequencies of two strings.
Longest Substring Without Repeating Characters
Variable window with a distinctness constraint instead of a fixed-size count match.

Same pattern

←

Minimum Window Substring

Continue · Next problem

Minimum Size Subarray Sum

mediumStringsLC #567Frequently asked

Permutation in String

LCPractice

Sliding Window · 5 of 6 · 9 min

Given two strings s1 and s2, return true if s2 contains a permutation of s1, or false otherwise.

In other words, return true if one of s1's permutations is a substring of s2.

In plain English

Examples

Example 1

Input: s1 = "ab", s2 = "eidbaooo"
Output: true
Note: s2 contains "ba" at indices 3–4, which is a permutation of "ab".

Example 2

Input: s1 = "ab", s2 = "eidboaoo"
Output: false
Note: No length-2 window of s2 has counts {a:1, b:1}.

Example 3

Input: s1 = "adc", s2 = "dcda"
Output: true
Note: "dca" (indices 1–3) is a permutation of "adc".

Constraints

1 ≤ s1.length, s2.length ≤ 10⁴
s1 and s2 consist of lowercase English letters

Clarifying questions4First question: Does the permutation have to be contiguous in s2?Explore questions

Q1.Does the permutation have to be contiguous in s2?
Yes — it must appear as a substring (a contiguous block), not a scattered subsequence.
Q2.What defines a permutation match?
Same length and identical character frequencies as s1; order doesn't matter.
Q3.What if s1 is longer than s2?
No window of length |s1| fits in s2, so return false immediately.
Q4.What's the alphabet?
Lowercase English letters — a fixed 26-slot count array, so space is O(1).

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Where candidates slip

Re-sorting or rebuilding the count map for every window (O(|s1|) per slide), or forgetting the add-and-remove pairing so the window drifts off its fixed size.

How to stand out

Choose

Compare the available approaches

Use constraints and trade-offs to select the route you can defend in an interview.

Approaches at a glanceCompare before you dive in

#	Approach	Time	Space	When to mention	Jump
1	Brute Force — Recount Every Window	`O(\|s2\| · \|s1\|)`	`O(1)`	Say it first to anchor the baseline and to make 'permutation = equal counts' explicit.	Read
2	Fixed-Size Sliding Window of Counts (Optimal)Optimal	`O(\|s2\|)`	`O(1)`	The answer they want. Phrase it as 'slide a window of length \|s1\|, adding the entering char and removing the leaving one, comparing counts'.	Read

Learn & trace

Build each solution step by step

Move from the core idea to a visual trace, implementation, proof, and edge cases.

03.1

Approach 1 of 2

Brute Force — Recount Every Window

TimeO(|s2| · |s1|)SpaceO(1)

Say it first to anchor the baseline and to make 'permutation = equal counts' explicit.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

A permutation of s1 has the same length as s1. So only substrings of s2 of length |s1| can match.

2Hint 2Explore hint

For each such window, count its characters (or sort it) and compare to s1's counts (or sorted s1).

3Hint 3Explore hint

Scan all windows and return true on the first match. Each window recount is O(|s1|) — that's the inefficiency to remove.

A · Core idea

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

s1 = "ab", s2 = "eidba"

"ei"

{e:1,i:1} ≠ need

Stateno

Final resulttrue

C · Code with teaching comments

solution.javaJava

Brute Force — Recount Every Window — reference

3 teaching notes

1
public boolean checkInclusion(String s1, String s2) {
2
    int len = s1.length();
3
    // No window of length |s1| fits — early exit.
4
    if (len > s2.length()) return false;
5
    int[] need = new int[26];
6
    for (char c : s1.toCharArray()) need[c - 'a']++;
7
    for (int i = 0; i + len <= s2.length(); i++) {
8
        int[] win = new int[26];
9
        // Recount the whole window — the O(|s1|) per-step waste.
10
        for (int j = i; j < i + len; j++) win[s2.charAt(j) - 'a']++;
11
        // Matching counts means this window is a permutation of s1.
12
        if (Arrays.equals(win, need)) return true;
13
    }
14
    return false;
15
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.15 lines

D · Why it works and complexityO(|s2| · |s1|) timeO(1) spaceOpen the invariant and proofExplore the proof

ComplexityO(|s2| · |s1|) time, O(1) space — There are O(|s2|) windows; counting each from scratch is O(|s1|), giving O(|s2|·|s1|). The count arrays are fixed 26 ints → O(1) space.

E · Edge cases and pitfalls3Recounting each window instead of sliding — the O(|s1|) per-step cost.Explore edge cases

Pitfalls

Recounting each window instead of sliding — the O(|s1|) per-step cost.
Comparing as sorted strings repeatedly, which is even slower (O(|s1| log |s1|) per window).
Missing the |s1| > |s2| early exit, risking out-of-range windows.

03.2

Approach 2 of 2 · Optimal

Fixed-Size Sliding Window of Counts (Optimal)

TimeO(|s2|)SpaceO(1)

The answer they want. Phrase it as 'slide a window of length |s1|, adding the entering char and removing the leaving one, comparing counts'.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Both the target length (|s1|) and the comparison (equal counts) are fixed. Build s1's count array and an initial window of the first |s1| chars of s2.

2Hint 2Explore hint

Slide the window one step at a time: add the new right character's count and subtract the character that exits on the left. The window size stays |s1|.

3Hint 3Explore hint

To avoid re-comparing all 26 counts each slide, track a `matches` counter of how many of the 26 letters currently have equal counts in window and need; the window is a permutation when matches == 26.

A · Core idea

Why the early exit matters. If |s1| > |s2|, no window fits and the answer is immediately false; this also prevents constructing an out-of-range initial window.

Why O(|s2|) time and O(1) space. Each character of s2 enters and leaves the window at most once, and the only storage is two constant-size count arrays plus the matches counter.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

s1 = "ab", s2 = "eidbaooo"

Array state

i=0..1

window "ei" — counts ≠ need

l ↓

[0]

r ↓

[1]

[2]

[3]

[4]

[5]

[6]

[7]

Current pointerResolved stateNot processed

Final resulttrue

C · Code with teaching comments

solution.javaJava

Fixed-Size Sliding Window of Counts (Optimal) — optimal

5 teaching notes

1
public boolean checkInclusion(String s1, String s2) {
2
    int len = s1.length();
3
    if (len > s2.length()) return false;
4
    int[] need = new int[26];
5
    int[] window = new int[26];
6
    for (int i = 0; i < len; i++) {
7
        need[s1.charAt(i) - 'a']++;
8
        window[s2.charAt(i) - 'a']++;
9
    }
10
    int matches = 0;
11
    for (int x = 0; x < 26; x++) {
12
        // Initialize matches = number of letters whose counts already agree.
13
        if (window[x] == need[x]) matches++;
14
    }
15
    for (int i = len; i < s2.length(); i++) {
16
        if (matches == 26) return true;
17
        int in = s2.charAt(i) - 'a';
18
        int out = s2.charAt(i - len) - 'a';
19
        window[in]++;
20
        if (window[in] == need[in]) matches++;
21
        // Overshot the target → that letter no longer matches.
22
        else if (window[in] == need[in] + 1) matches--;
23
        window[out]--;
24
        if (window[out] == need[out]) matches++;
25
        else if (window[out] == need[out] - 1) matches--;
26
    }
27
    // All 26 letters agree → the final window is a permutation of s1.
28
    return matches == 26;
29
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.29 lines

D · Why it works and complexityO(|s2|) timeO(1) spaceOpen the invariant and proofExplore the proof

E · Edge cases and pitfalls6s1 = "a", s2 = "a" — Window of size 1 equals need immediately → returns true before any slide.Explore edge cases

Edge cases handled

s1 = "a", s2 = "a"Window of size 1 equals need immediately → returns true before any slide.
s1 = "ab", s2 = "a"|s1| > |s2| → early return false.
s1 = "abc", s2 = "ccccbbbbaaaa"No length-3 window mixes a,b,c equally → returns false.

Pitfalls

Forgetting to check matches/equality for the initial window before sliding (missing a match at index 0).
Updating matches with wrong threshold logic (the need[x] ± 1 boundary conditions).
Not pairing every add with a remove, letting the window size drift away from |s1|.

Practice

Try the solution yourself

Edit the optimal implementation, test another input, and observe the result.

Try it — Java· run a complete program; method snippets need a driver

Avoid mistakes

Recognize the interview traps

Understand why common attempts fail before reviewing the corrected implementation.

Rebuilding the window each step

Adjacent windows overlap in all but two characters; recounting from scratch is O(|s1|) per step and defeats the point of a sliding window.

Explore the code comparison

Don't write this

for i in range(len(s2) - length + 1):
    win = [0] * 26
    for j in range(i, i + length):
        win[ord(s2[j]) - ord('a')] += 1

Write this instead

window[ord(s2[i]) - ord('a')] += 1
window[ord(s2[i - length]) - ord('a')] -= 1

Comparing strings instead of counts

A permutation is defined by equal frequencies, not order. Sorting each window to compare is correct but slower than count comparison.

Explore the code comparison

Don't write this

char[] a = window.toCharArray();
Arrays.sort(a);
if (new String(a).equals(sortedS1)) return true;

Write this instead

if (Arrays.equals(window, need)) return true;

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Fixed-size sliding window of frequency counts

Code pattern to memorize

if len(s1) > len(s2): return False
need, win = [0]*26, [0]*26
for c in s1: need[c]++ 
for i in range(len(s1)): win[s2[i]]++
if win == need: return True
for i in range(len(s1), len(s2)):
    win[s2[i]] += 1
    win[s2[i-len(s1)]] -= 1
    if win == need: return True
return False

Rules to remember

1A permutation has the same length and same character counts — order is irrelevant.
2The window is fixed-size at |s1|; slide by adding the new char and removing the one that falls off.
3Compare counts, not strings — a 26-length count array comparison is O(1).
4Early-exit false if |s1| > |s2| (no window can fit).
5A matches/required counter avoids re-comparing all 26 slots each slide for true O(|s2|).

Use this pattern when

Detect an anagram/permutation as a contiguous substring
The target window size is known and fixed
Equality of multisets can be tracked incrementally as the window slides
Fixed-length 'does this pattern appear (reordered)' substring problems

Choose another pattern when

Window size varies with a constraint → variable sliding window (LC3, LC76)
t must appear in order → substring search (KMP), not anagram matching
Need all matching positions → same window, collect indices (LC438)

Interview takeaway

Continue

Transfer the pattern to another problem

Use a direct variation or pattern sibling to prove the idea is reusable.

Practice queueDirect variations and pattern siblings

Direct follow-ups

Find All Anagrams in a String
Coming soon
Same fixed-size window, but collect every start index where counts match instead of returning on the first.
Minimum Window Substring
Variable window that must cover (not equal) t — grow then shrink.
Valid Anagram
The count-equality test without the window — just compare frequencies of two strings.
Longest Substring Without Repeating Characters
Variable window with a distinctness constraint instead of a fixed-size count match.

Same pattern

←

Minimum Window Substring

Continue · Next problem

Minimum Size Subarray Sum