Permutation In String

A permutation of s1 is just any rearrangement of the same characters, so checking “does s2 contain a permutation of s1” is the same as checking “does some substring of s2 of length len(s1) have the exact same character counts as s1”. That reframing turns this into a fixed-size sliding window problem: slide a window of length len(s1) across s2 and compare character-count arrays.

Brute Force (Sort and Compare)

Time O((n - m) · m log m)Space O(m)

For every window of length len(s1) in s2, sort both the window and s1 and compare.

class Solution:
    def checkInclusion(self, s1: str, s2: str) -> bool:
        n1, n2 = len(s1), len(s2)
        target = sorted(s1)
        for i in range(n2 - n1 + 1):
            if sorted(s2[i:i + n1]) == target:
                return True
        return False

Why it’s slow: there are O(n2 - n1) windows, and sorting each one costs O(n1 log n1), plus slicing the substring itself is O(n1). All of that work is wasted, since sliding by one position only changes the window by one character in and one character out.

Sliding Window (Fixed-Size Frequency Count)

OptimalTime O(n1 + 26 · n2)Space O(1)

Build a 26-length frequency array for s1, then a matching frequency array for the first window of s2. Slide the window one character at a time: add the new right character, remove the old left character, and compare the two 26-length arrays. Since the alphabet is fixed at 26 letters, this comparison is O(1) amortized in practice (or an explicit O(26) worst case), not proportional to the window length.

class Solution:
    def checkInclusion(self, s1: str, s2: str) -> bool:
        n1, n2 = len(s1), len(s2)
        if n1 > n2:
            return False

        need = [0] * 26
        window = [0] * 26
        for ch in s1:
            need[ord(ch) - 97] += 1
        for i in range(n1):
            window[ord(s2[i]) - 97] += 1

        if window == need:
            return True

        for right in range(n1, n2):
            window[ord(s2[right]) - 97] += 1
            left_ch = s2[right - n1]
            window[ord(left_ch) - 97] -= 1
            if window == need:
                return True
        return False

Tracing s1 = "ab", s2 = "eidbaooo": watch the s2 window slide one character at a time while the need and window count vectors stay in lockstep — a match is exactly when the two vectors become identical.

need (s1)

a1b1d0e0i0

window

a0b0d0e0i0

window vs needbuilding need

1 / 6

comparingcurrentdiscardedresult

need counts s1 = ab: a:1 b:1. Every window has length 2, so a match needs exactly these counts.

Correctness: two strings of equal length are permutations of each other exactly when their character-count arrays are identical. The sliding window always maintains the exact frequency array of the current len(s1)-length substring, so the comparison is exact — no false positives or negatives.

Complexity: building the initial arrays is O(n1). Each subsequent slide does O(1) work to update counts plus an O(26) array comparison, repeated n2 - n1 times — O(n1 + 26 · n2) time, which simplifies to O(n1 + n2). Space is O(1) since the frequency arrays are fixed at size 26.

Permutation In String

Brute Force (Sort and Compare)

Sliding Window (Fixed-Size Frequency Count)

More Sliding Window practice