Problem Statement

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.

Additional information

• 1 <= s1.length, s2.length <= 10^4
• s1 and s2 consist of lowercase English letters.

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

Brute Force

Intuition
A permutation of a string is simply a rearrangement of its characters. The brute force approach is to generate every possible permutation of s1 and check if any of them appear as a substring in s2.

Algorithm

1. Generate all permutations of s1.
2. For each permutation, check if it is a substring of s2.
3. If found, return True.
4. If no permutation is found after checking all, return False.

def check_inclusion(s1: str, s2: str) -> bool:
    from itertools import permutations
    
    perms = [''.join(p) for p in permutations(s1)]
    for p in perms:
        if p in s2:
            return True
            
    return False

Time & Space Complexity

• Time complexity: O(n! * m)

• Reason: Generating all permutations of s1 (length n) takes O(n!). Checking each permutation in s2 (length m) takes O(m). This is highly inefficient for n > 10.

• Space complexity: O(n!)

• Reason: Storing all permutations.

Hash Table (Sliding Window)

Intuition

A string s2 contains a permutation of s1 if any substring of s2 has the exact same character counts as s1. We can use two Hash Tables (dictionaries) to store these counts: one for s1 and one for the current window in s2.

We slide a window of length len(s1) across s2. At each step, we update the hash table for the window (add the new character on the right, remove the old character on the left) and simply compare if window_counts == s1_counts.

Algorithm

1. If len(s1) > len(s2), return False.

2. Create a Hash Map s1_count for s1.

3. Create a Hash Map window_count for the first len(s1) characters of s2.

4. If s1_count == window_count, return True.

5. Iterate i from len(s1) to len(s2) - 1:

   • Add the new character s2[i] to window_count.

   • Remove the old character s2[i - len(s1)] from window_count. If its count drops to 0, verify we delete the key to ensure the dictionaries match perfectly.

   • Check if s1_count == window_count.

6. If no match is found after the loop, return False.

from collections import Counter

def check_inclusion(s1: str, s2: str) -> bool:
    if len(s1) > len(s2):
        return False

    s1_count = Counter(s1)
    window_count = Counter(s2[:len(s1)])

    if s1_count == window_count:
        return True

    for i in range(len(s1), len(s2)):
        # Add the new character to the window
        window_count[s2[i]] += 1
        
        # Remove the old character from the left of the window
        left_char = s2[i - len(s1)]
        window_count[left_char] -= 1
        if window_count[left_char] == 0:
            del window_count[left_char]  # Remove key to allow '==' comparison

        if s1_count == window_count:
            return True

    return False

Time & Space Complexity

• Time complexity: O(26 * n) which simplifies to O(n).

  • Reason: We iterate through s2 once. In Python, comparing two dictionaries takes time proportional to the number of keys. Since the input is limited to lowercase English letters, there are at most 26 keys. Thus, the comparison is O(1).

• Space complexity: O(1)

  • Reason: The Hash Maps store at most 26 characters (lowercase English letters).

Sliding Window (Optimal)

Intuition
Instead of generating permutations, we can characterize a permutation by its character counts. Two strings are permutations of each other if and only if they have the exact same frequency of every character.

We can use a sliding window of size len(s1) on s2. As the window slides from left to right, we update the character counts of the current window. If the counts of the window match the counts of s1, we found a permutation.

Algorithm

1. If len(s1) > len(s2), return False.
2. Create frequency arrays (or hash maps) for s1 and the first window of s2 (length len(s1)).
3. Compare the two frequency arrays. If they match, return True.
4. Slide the window one character at a time from len(s1) to len(s2):

• Add the new character entering the window to the s2 count.
• Remove the character leaving the window from the s2 count.
• Compare the arrays again. If match, return True.

5. Return False if no match is found.

def check_inclusion(s1: str, s2: str) -> bool:
    if len(s1) > len(s2):
        return False
    
    s1_count = [0] * 26
    s2_count = [0] * 26
    
    for i in range(len(s1)):
        s1_count[ord(s1[i]) - ord('a')] += 1
        s2_count[ord(s2[i]) - ord('a')] += 1
        
    matches = 0
    for i in range(26):
        if s1_count[i] == s2_count[i]:
            matches += 1
            
    l = 0
    for r in range(len(s1), len(s2)):
        if matches == 26:
            return True
        
        index = ord(s2[r]) - ord('a')
        s2_count[index] += 1
        if s1_count[index] == s2_count[index]:
            matches += 1
        elif s1_count[index] + 1 == s2_count[index]:
            matches -= 1
            
        index = ord(s2[l]) - ord('a')
        s2_count[index] -= 1
        if s1_count[index] == s2_count[index]:
            matches += 1
        elif s1_count[index] - 1 == s2_count[index]:
            matches -= 1
            
        l += 1
        
    return matches == 26

Time & Space Complexity

• Time complexity: O(n)

• Reason: We slide the window across s2 once (O(n)). The comparisons inside the loop are constant time (26 characters).

• Space complexity: O(1)

• Reason: The frequency arrays are fixed size (26).