Leetcode - 567. Permutation in String

Medium

Dec 22, 2025

#sliding-window

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

1 <= s1.length, s2.length <= 104
s1 and s2 consist of lowercase English letters.

Constraints:

Notes

Intuition

A permutation of s1 in s2 means a substring of s2 has the exact same character frequencies as s1. Slide a fixed-size window across s2 and check if frequencies match.

Implementation

Use a single frequency array. First, increment for each character in s1, then decrement for the first len(s1) characters of s2. If all zeros, we found a match. Slide the window: increment the count of the character leaving (left), decrement the count of the character entering (right). Check for all zeros at each position.

Edge-cases

Return early if len(s1) > len(s2). Don't forget to check for a match after the final window position (after the loop exits).

Time: O(n) — single pass through s2
Space: O(1) — frequency array is fixed at 26 elements

Complexity

Solution

class Solution:
    def char2idx(self, c: str) -> int:
        return ord(c) - ord('a')

    def checkInclusion(self, s1: str, s2: str) -> bool:
        if len(s1) > len(s2):
            return False
        freq = [0] * 26
        for c in s1:
            freq[self.char2idx(c)] += 1

        for i in range(len(s1)):
            freq[self.char2idx(s2[i])] -= 1

        l, r = 0, len(s1)

        while r < len(s2):
            if all(x == 0 for x in freq):
                return True
            
            # Leaving window
            freq[self.char2idx(s2[l])] += 1
            # Entering window
            freq[self.char2idx(s2[r])] -= 1
            l += 1
            r += 1


        return all(x == 0 for x in freq)
        



if __name__ == "__main__":
    # Include one-off tests here or debugging logic that can be run by running this file
    # e.g. print(solution.two_sum([1, 2, 3, 4], 3))
    solution = Solution()