LeetEye LeetEye
Medium Sliding Window ~5 min

Permutation in String

sliding-window permutation-in-string

Problem

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.

Examples

Example 1
Input: s1 = "ab", s2 = "eidbaooo"
Output: true
s2 contains one permutation of s1 ("ba").
Example 2
Input: s1 = "ab", s2 = "eidboaoo"
Output: false
Key Insight

A permutation has the same characters in different order. Same characters = same frequency count.

Permutation = same frequency. Slide fixed-size window, update counts incrementally, check for match.

How to Approach This Problem

Pattern Recognition: When you see keywords like permutation in string sliding-window, think Sliding Window.

Step-by-Step Reasoning

1 Two strings are permutations of each other if:
Answer: They have identical character frequency counts
"abc" and "bca" are permutations — same chars, same counts, different order.
2 For s1 of length n, generating all permutations takes:
Answer: O(n!) time
n! permutations exist. For n=10, that's 3.6 million. Way too slow.
3 To find a permutation of s1 in s2, the window size should be:
Answer: len(s1)
Permutation has exact same length as original. Window must match s1's length.
4 With a fixed-size window, when we slide right by 1:
Answer: Add new char on right, remove old char on left
Sliding by 1 = one char enters (right), one char exits (left). Update counts incrementally.
5 The simplest way to check if window matches s1:
Answer: Compare frequency dictionaries
Two frequency maps can be compared in O(26) = O(1) for lowercase letters.
6 Instead of comparing full maps, we can track:
Answer: Number of matching character counts
Track how many of the 26 characters have matching counts. When all 26 match (or all present chars match), we found a permutation.

Solution

def checkInclusion(s1: str, s2: str) -> bool:
    if len(s1) > len(s2):
        return False
    
    s1_count = [0] * 26
    window_count = [0] * 26
    
    for c in s1:
        s1_count[ord(c) - ord('a')] += 1
    
    for i in range(len(s2)):
        # Add char to window
        window_count[ord(s2[i]) - ord('a')] += 1
        
        # Remove char that left the window
        if i >= len(s1):
            window_count[ord(s2[i - len(s1)]) - ord('a')] -= 1
        
        # Check if window matches s1
        if window_count == s1_count:
            return True
    
    return False

Complexity Analysis

Time O(n)
Space O(1)

Master This Pattern

Build intuition with interactive MCQs. Practice Sliding Window problems in the LeetEye app.

Download LeetEye Free
Practice in LeetEye