Permutation in String — Solution

Problem

Given two strings, determine whether the second string contains any permutation of the first string as a contiguous substring. A permutation is a rearrangement of all characters, so "ab" and "ba" are both permutations of each other.

• Input: s1 = "ab", s2 = "eidbaooo"
• Output: true
• Explanation: "ba" at index 3–4 in s2 is a permutation of s1.

Counter-example: s1 = "ab", s2 = "eidboaoo" → false. The letters 'a' and 'b' never appear together in the same window.

Intuition

Two strings are permutations of each other if and only if they have identical character frequencies. Instead of generating every permutation of s1 (exponentially expensive), slide a window of exactly len(s1) characters across s2 — this window visits every candidate substring of the right length. The trick is maintaining a counter that tracks how many of the 26 characters currently have matching frequencies in the window and in s1; when all 26 match, the window is a permutation.

Solution — Fixed Sliding Window with Match Counter

Build a character frequency table for s1. Slide a window of the same length over s2, updating frequencies one character at a time. Before each update, check if the exiting or entering character was already contributing to the match count; after the update, check again — this way the match counter stays correct with O(1) work per step.

1. Return false early if s1 is longer than s2 (no window can fit).
2. Build s1_freq[26] from s1. Build window_freq[26] from the first len(s1) characters of s2.
3. Initialize matches = number of indices where both frequency arrays agree.
4. If matches == 26, return true immediately.
5. For each new character entering the right edge of the window: decrement matches if the entering character's count was matching, update the count, increment matches if it now matches. Repeat the same logic for the character leaving the left edge.
6. Check matches == 26 after each slide; return false if the loop ends without a match.

1def checkInclusion(s1: str, s2: str) -> bool:
2    if len(s1) > len(s2):
3        return False
4
5    s1_freq = [0] * 26
6    window_freq = [0] * 26
7
8    for char in s1:
9        s1_freq[ord(char) - ord('a')] += 1
10
11    for i in range(len(s1)):
12        window_freq[ord(s2[i]) - ord('a')] += 1
13
14    # Count how many of the 26 characters already have equal frequencies
15    matches = sum(1 for i in range(26) if s1_freq[i] == window_freq[i])
16
17    if matches == 26:
18        return True
19
20    for i in range(len(s1), len(s2)):
21        entering = ord(s2[i]) - ord('a')
22        leaving = ord(s2[i - len(s1)]) - ord('a')
23
24        # Update match count for the character entering the right edge
25        if window_freq[entering] == s1_freq[entering]:
26            matches -= 1  # was matching, about to change
27        window_freq[entering] += 1
28        if window_freq[entering] == s1_freq[entering]:
29            matches += 1  # now matches after increment
30
31        # Update match count for the character leaving the left edge
32        if window_freq[leaving] == s1_freq[leaving]:
33            matches -= 1  # was matching, about to change
34        window_freq[leaving] -= 1
35        if window_freq[leaving] == s1_freq[leaving]:
36            matches += 1  # now matches after decrement
37
38        if matches == 26:
39            return True
40
41    return False

Time: O(|s1| + |s2|) — one pass to build s1's frequency table, one pass sliding the window; each step is O(1) work with the match counter.

Space: O(1) — two fixed-size arrays of 26 integers regardless of input length.

Complexity Summary

Common Mistakes

• Skipping the len(s1) > len(s2) guard — without it, the initial window loop reads past the end of s2 and the leaving-character index goes negative on the first slide.
• Updating the frequency before checking the match status — you must record whether the count was already matching before the increment or decrement, otherwise you miss the transition and the counter drifts.
• Using the wrong leaving index — the character leaving the window is at s2[i - len(s1)], not s2[i - 1]; confusing these produces a window of the wrong characters.
• Comparing the full frequency arrays on every step — replacing the 26-element comparison with a single integer check is the key optimization; without it the approach is still correct but O(26n) instead of O(n).
• Forgetting to check the initial window before the loop — if the first len(s1) characters of s2 already form a permutation, the loop never runs and the function incorrectly returns false.

Related Problems

• find-all-anagrams-in-a-string — identical sliding window structure, but collects all matching start indices instead of returning a boolean
• minimum-window-substring — same character frequency matching idea but the window shrinks and grows to find the smallest valid window
• longest-repeating-character-replacement — fixed window with a character count constraint, same incremental update pattern
• longest-substring-without-repeating-characters — sliding window maintaining a uniqueness constraint on character counts
• sliding-window-maximum — fixed-size window sliding over an array, different internal data structure but the same window advancement logic