Leetcode 567 - Permutation in String

Table of contents

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 <= 104 s1 and s2 consist of lowercase English letters.

Explanation/Approach

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]
            else:
                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

Explanation:

• We first count the frequency of each character in s1 using a Counter.
• Then, we iterate over s2, counting the frequency of characters within a window of length s1.length().
• For each character added to the window, if the window size exceeds s1.length(), we remove the leftmost character from the count.
• At each step, we compare the count of characters within the window to the count of characters in s1. If they match, we immediately return True.
• If we reach the end of s2 without finding a match, we return False.

Time and Memory Complexity:

• Time Complexity: O(N) where N is the length of s2. Each character in s2 is processed once.
• Space Complexity: O(1). The counter will have at most 26 keys (for each letter in the English alphabet), so it uses constant space.