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 the 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.

Solution

Approach: Sliding Window with Character Frequency

Two strings are permutations of each other if and only if they have the same character frequencies. So instead of generating permutations, slide a fixed window of size len(s1) through s2 and compare frequency maps at each position.

Implementation

from collections import Counter

class Solution:
    def checkInclusion(self, s1: str, s2: str) -> bool:
        s1_counts = Counter(s1)

        start = 0
        state = {}
        for i, char in enumerate(s2):
            state[char] = state.get(char, 0) + 1
            if i - start + 1 == len(s1):
                if s1_counts == state:
                    return True
                state[s2[start]] -= 1
                if state[s2[start]] == 0:
                    del state[s2[start]]
                start += 1
        return False

The window grows until it reaches size len(s1), then starts sliding. On each slide, we add the new right character, check for a match, then remove the left character. Deleting zero-count entries keeps the dictionary clean so == comparison works correctly.

Complexity Analysis

Time Complexity: O(n), where n is the length of s2. Each character is added and removed from the window once. The dictionary comparison is O(1) since it contains at most 26 lowercase letters.
Space Complexity: O(1), since both dictionaries store at most 26 entries.

Key Insights

Permutation = Same Frequency: Two strings are permutations of each other if and only if they have the same character frequencies. No need to generate permutations.
Single Loop: The window initialization and sliding happen in one loop. The window grows until it hits len(s1), then slides forward, avoiding duplicated logic for the initial window.
Clean Zero Entries: Deleting keys with zero counts is essential. Without it, {"a": 1} and {"a": 1, "b": 0} would compare as unequal, causing false negatives.