LeetCode Solutions Blog

Permutation in String

Number: 567

Difficulty: Medium

Paid? No

Problem Description

Given two strings s1 and s2, determine if s2 contains any permutation of s1 as a substring. In other words, check if one of s1's rearrangements exists within s2.

Key Insights

Use a sliding window approach to examine substrings of s2 of length equal to s1.
Maintain frequency counts of characters for both s1 and the current window in s2.
Compare the frequency counts to determine if a valid permutation exists.
Increment the window by adding a new character and removing the leftmost one, keeping the operation efficient.

Space and Time Complexity

Time Complexity: O(n) where n is the length of s2 (each character is processed a constant number of times).
Space Complexity: O(1) since the frequency count arrays have a fixed size (26 for lowercase English letters).

Solution

The solution uses two fixed-length arrays (of size 26) to store character frequencies for s1 and the current window in s2. First, initialize the frequency arrays by processing s1 and the first window of s2. Then, slide the window one character at a time, updating the counts by incrementing the count for the new character and decrementing the count for the character that is no longer in the window. After each move, compare both frequency arrays; if they match, s2 contains a permutation of s1. This technique avoids repeatedly computing the frequency distribution from scratch, making the algorithm efficient.

Code Solutions

# Python solution with line-by-line comments

def checkInclusion(s1: str, s2: str) -> bool:
    # Get lengths of the input strings
    len1, len2 = len(s1), len(s2)
    # Edge case: s1 cannot be a substring if longer than s2
    if len1 > len2:
        return False

    # Initialize frequency arrays for s1 and for the first window of s2
    s1_count = [0] * 26
    window_count = [0] * 26

    # Build frequency counts for s1 and the initial window in s2
    for i in range(len1):
        s1_count[ord(s1[i]) - ord('a')] += 1
        window_count[ord(s2[i]) - ord('a')] += 1

    # Check if initial window is a permutation of s1
    if s1_count == window_count:
        return True

    # Slide the window across s2, updating the counts on the fly
    for i in range(len1, len2):
        # Add the new character from the right end of the window
        window_count[ord(s2[i]) - ord('a')] += 1
        # Remove the character that is no longer in the window
        window_count[ord(s2[i - len1]) - ord('a')] -= 1

        # Check if current window matches s1's frequency distribution
        if window_count == s1_count:
            return True

    return False

# Example usage:
# print(checkInclusion("ab", "eidbaooo"))  # Expected output: True