DSAPrep
MediumSliding Window

Permutation In String

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.

Example 1

Input: s1 = "ab", s2 = "eidbaooo"
Output: true
Explanation: s2 contains one permutation of s1 ("ba").

Example 2

Input: s1 = "ab", s2 = "eidboaoo"
Output: false

Constraints

  • 1 <= s1.length, s2.length <= 10^4
  • s1 and s2 consist of lowercase English letters.
View original on LeetCode ↗

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":

left
e
0
right
i
1
d
2
b
3
a
4
o
5
o
6
o
7
window = eimatches = no
1 / 4
comparingseenresultdiscarded

Initial window [0,1] = ei. Counts do not match ab.

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.