Skip to content

Leetcode 567 - Permutation in String

Difficulty: medium

Table of contents

Open Table of contents


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.


The problem requires checking if there is any permutation of string s1 that is a substring of s2. This means you have to check if all characters (and their respective counts) in s1 are present consecutively in s2.

One efficient approach to solve this problem involves using a sliding window with a hashmap (or frequency counter). We can iterate over s2 with a window of size s1.length(), and check if the frequency of characters within this window matches that of s1.

Approach Steps:

  1. First, count the frequency of each character in s1 and store it in a hashmap.
  2. Create a sliding window over s2 of length s1.length().
  3. Count the frequency of characters within the sliding window and compare it to the frequency hashmap of s1.
  4. If both frequency maps are equal, return true.
  5. Otherwise, continue sliding the window over s2 and update the frequency counts accordingly until you find a match or reach the end of s2.

Solution (Sliding Window Approach)

Below is the detailed code explanation for the sliding window approach.

from collections import Counter

def check_inclusion(s1: str, s2: str) -> bool:
    # Step 1: Count frequency of each character in s1
    s1_count = Counter(s1)

    # Step 2: Initialize a sliding window and count characters
    window_count = Counter()
    for i, c in enumerate(s2):
        window_count[c] += 1

        # Step 3: If the window size is greater than s1's length, remove leftmost character from count
        if i >= len(s1):
            left_char = s2[i - len(s1)]
            if window_count[left_char] == 1:
                del window_count[left_char]
                window_count[left_char] -= 1

        # Step 4: Compare window_count and s1_count. If they're equal, return True
        if window_count == s1_count:
            return True

    return False  # If loop finishes and no return, then no valid substring found


Time and Memory Complexity: