Permutation in String: Fixed-Size Sliding Window with Frequency Matching

LeetCode 567, Permutation in String, asks whether s2 contains any permutation of s1 as a substring. In other words, you need to find a contiguous window in s2 whose characters are exactly a rearrangement of s1.

This is one of the cleanest examples of a fixed-size sliding window. Unlike problems where the window grows and shrinks, here the window is always the same length as s1. You slide it across s2 one character at a time and check whether the character frequencies match.

The problem

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

• s1 = "ab", s2 = "eidbaooo" returns true because s2 contains "ba", which is a permutation of "ab".
• s1 = "ab", s2 = "eidboaoo" returns false because no contiguous window of length 2 in s2 has the same characters as "ab".

The approach

The brute force way would be to generate every permutation of s1 and check if any of them appears in s2. But s1 can have up to 10^4 characters, and the number of permutations is factorial. That is not going to work.

The key insight is that you do not care about the order of characters. Two strings are permutations of each other if and only if they have the same character frequencies. So instead of generating permutations, you compare frequency maps.

Here is the plan:

1. Build a frequency map for s1.
2. Create a sliding window of length len(s1) over s2.
3. Maintain a frequency map for the current window.
4. Each time you slide, add the new character entering from the right and remove the character leaving from the left.
5. If the window frequency matches the s1 frequency, return true.

Since the window size is fixed, you never need to grow or shrink it. You just slide it one position to the right on each step.

The solution

from collections import Counter

def checkInclusion(s1, s2):
    if len(s1) > len(s2):
        return False

    s1_count = Counter(s1)
    window_count = Counter(s2[:len(s1)])

    if s1_count == window_count:
        return True

    for i in range(len(s1), len(s2)):
        window_count[s2[i]] += 1
        left_char = s2[i - len(s1)]
        window_count[left_char] -= 1
        if window_count[left_char] == 0:
            del window_count[left_char]
        if s1_count == window_count:
            return True

    return False

Let's walk through the logic:

1. If s1 is longer than s2, no permutation can possibly fit. Return false immediately.
2. Build the frequency map for s1 using Counter.
3. Build the initial window frequency map from the first len(s1) characters of s2.
4. If they match right away, return true.
5. Otherwise, slide the window one character at a time. Add the new right character, remove the old left character. If a character's count drops to zero, delete it from the map so the equality comparison works cleanly.
6. Check for a match after each slide.

Step-by-step walkthrough

Let's trace through s1 = "ab" and s2 = "eidbaooo". The window size is 2, and we need to find a window where the frequency map equals {a:1, b:1}.

We found a match at window [3,4]. The substring "ba" has frequency {b:1, a:1}, which equals {a:1, b:1}. Return true.

Complexity analysis

Time: O(n) where n is the length of s2. You slide the window across s2 once. Each slide does O(1) work: one dictionary increment, one decrement, and one comparison. The comparison itself is O(1) because the frequency maps have at most 26 entries (lowercase English letters), so comparing them is bounded by a constant.

Space: O(1). Both frequency maps hold at most 26 entries. This does not grow with input size.

Here n is len(s1) and m is len(s2).

The building blocks

This problem decomposes into two reusable pieces that CodeBricks drills independently:

1. Fixed-size sliding window

Unlike variable-size sliding windows (where the window grows and shrinks based on a condition), this window is always exactly len(s1) characters wide. The rhythm is simple: add from the right, remove from the left, always maintaining the same size.

for i in range(len(s1), len(s2)):
    window_count[s2[i]] += 1
    left_char = s2[i - len(s1)]
    window_count[left_char] -= 1
    if window_count[left_char] == 0:
        del window_count[left_char]

This same fixed-window pattern appears in Find All Anagrams in a String (where you collect all matching indices instead of returning on the first one) and in any problem where you need to check a property over every substring of a given length.

2. Frequency matching

Instead of comparing strings character by character or sorting them, you compare their frequency maps. Two strings are anagrams (permutations of each other) if and only if they produce the same frequency map. This is O(1) to check when the alphabet is fixed.

s1_count = Counter(s1)
if s1_count == window_count:
    return True

This frequency-matching technique shows up in Group Anagrams, Valid Anagram, and anywhere you need to check if two collections of characters are equivalent regardless of order.

Edge cases

Before submitting, verify your solution handles:

• s1 longer than s2: return false immediately. No window of length len(s1) can exist.
• Single character: s1 = "a", s2 = "a". The initial window matches right away.
• s1 equals s2: same length strings. The initial window is the entire string. Compare once and return.
• All same characters: s1 = "aaa", s2 = "aaaaaaa". Every window matches. Return true on the first check.
• No match at all: s1 = "ab", s2 = "eidboaoo". Slide through every window and return false at the end.

The sliding window solution handles all of these without special cases beyond the initial length check.

From understanding to recall

Reading through this solution is one thing. Reproducing it from a blank editor in a week is another. The gap between "I understand it" and "I can write it" is where most people get stuck in interviews. Spaced repetition closes that gap: you revisit the fixed-size-sliding-window and frequency-matching building blocks at increasing intervals, writing the code each time, until the pattern is something you assemble from muscle memory rather than reconstruct from scratch.

Related posts

• Find All Anagrams in a String - The same fixed-size window and frequency matching, but collecting all matching indices instead of stopping at the first
• Minimum Window Substring - A variable-size sliding window with frequency tracking, the harder cousin of this problem
• Longest Repeating Character Replacement - Another frequency-based sliding window that uses a grow-and-shrink approach

Each of these problems uses the same core idea of maintaining a frequency map inside a sliding window. Once you internalize that pattern here, the others become variations on a theme you already know.