Permutation in String medium

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 the anagrams of s1 is a 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

Steps

1. Character Count: Create a dictionary to store the frequency of each character in s1.
2. Sliding Window: Use a sliding window of size len(s1) to traverse s2.
3. Frequency Check: For each window in s2, create a dictionary to store the frequency of characters within that window.
4. Comparison: Compare the frequency dictionaries of s1 and the current window. If they are identical, a permutation is found.
5. Update Window: Slide the window one position to the right.

Explanation

The core idea is to efficiently check if a substring of s2 has the same character frequencies as s1. Instead of generating all permutations of s1 (which is computationally expensive), we directly compare character frequencies. The sliding window technique allows us to process s2 efficiently by reusing frequency counts from the previous window, avoiding redundant calculations.

Code

from collections import Counter

def checkInclusion(s1, s2):
    """
    Checks if s2 contains a permutation of s1.

    Args:
        s1: The string to find a permutation of.
        s2: The string to search within.

    Returns:
        True if s2 contains a permutation of s1, False otherwise.
    """
    len_s1 = len(s1)
    len_s2 = len(s2)

    if len_s1 > len_s2:
        return False

    count_s1 = Counter(s1)  # Count character frequencies in s1

    window = {}  # Count character frequencies in the sliding window
    for i in range(len_s1):
        window[s2[i]] = window.get(s2[i], 0) + 1

    if window == count_s1:  # Check if the initial window is a permutation
        return True

    # Slide the window through s2
    for i in range(len_s1, len_s2):
        window[s2[i]] = window.get(s2[i], 0) + 1  # Add the new character
        window[s2[i - len_s1]] -= 1  # Remove the old character
        if window[s2[i - len_s1]] == 0:
            del window[s2[i - len_s1]]  # Remove from dictionary if count is 0

        if window == count_s1:  #Check if the current window is a permutation
            return True

    return False

Complexity

• Time Complexity: O(len(s2)), as we iterate through s2 once using the sliding window. The operations within the loop (dictionary updates and comparisons) are O(1) on average.
• Space Complexity: O(1), as the dictionaries count_s1 and window store at most a fixed number of characters (the size of the alphabet). In the worst case, it depends on the size of the alphabet used in the strings. If the alphabet is small (e.g., lowercase English letters), it is considered O(1) space. If the alphabet is large or potentially unbounded, it is considered O(min(len(s1), len(s2)) space.