Permutation in String

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

Solution

Approach: Sliding Window with Character Frequency

The key insight is that two strings are permutations of each other if they have the same character frequencies. We can use a sliding window of size len(s1) on s2 and check if the character frequencies match.

We maintain:

s1_count: frequency map of characters in s1
window_count: frequency map of characters in the current window of s2
A window of size len(s1) that slides through s2

Implementation

class Solution:
    def checkInclusion(self, s1: str, s2: str) -> bool:
        if len(s1) > len(s2):
            return False

        # Count characters in s1
        s1_count = {}
        for char in s1:
            s1_count[char] = s1_count.get(char, 0) + 1

        # Initialize window
        window_count = {}
        for i in range(len(s1)):
            char = s2[i]
            window_count[char] = window_count.get(char, 0) + 1

        # Check if initial window matches
        if window_count == s1_count:
            return True

        # Slide the window
        for i in range(len(s1), len(s2)):
            # Add new character
            new_char = s2[i]
            window_count[new_char] = window_count.get(new_char, 0) + 1

            # Remove old character
            old_char = s2[i - len(s1)]
            window_count[old_char] -= 1
            if window_count[old_char] == 0:
                del window_count[old_char]

            # Check if window matches
            if window_count == s1_count:
                return True

        return False

Optimized Version (Using Array for Lowercase Letters):

class Solution:
    def checkInclusion(self, s1: str, s2: str) -> bool:
        if len(s1) > len(s2):
            return False

        # Use arrays for character counts (26 lowercase letters)
        s1_count = [0] * 26
        s2_count = [0] * 26

        # Count s1 and first window of s2
        for i in range(len(s1)):
            s1_count[ord(s1[i]) - ord('a')] += 1
            s2_count[ord(s2[i]) - ord('a')] += 1

        # Track number of matching character frequencies
        matches = 0
        for i in range(26):
            if s1_count[i] == s2_count[i]:
                matches += 1

        # Slide the window
        left = 0
        for right in range(len(s1), len(s2)):
            if matches == 26:
                return True

            # Add right character
            index = ord(s2[right]) - ord('a')
            s2_count[index] += 1
            if s2_count[index] == s1_count[index]:
                matches += 1
            elif s2_count[index] == s1_count[index] + 1:
                matches -= 1

            # Remove left character
            index = ord(s2[left]) - ord('a')
            s2_count[index] -= 1
            if s2_count[index] == s1_count[index]:
                matches += 1
            elif s2_count[index] == s1_count[index] - 1:
                matches -= 1

            left += 1

        return matches == 26

Complexity Analysis

Time Complexity: O(n), where n is the length of s2. We process each character once in the sliding window.
Space Complexity: O(1), since we only store counts for at most 26 lowercase English letters.

Key Insights

Permutation = Same Frequency: Two strings are permutations of each other if and only if they have the same character frequencies. We don’t need to generate all permutations.
Fixed Window Size: The window size is fixed at len(s1). We slide this window through s2 and check frequencies at each position.
Optimization with Matches Counter: Instead of comparing entire frequency maps at each step, we can track the number of matching character frequencies. When matches equals 26, we have a permutation.
Dictionary vs Array: Using a dictionary is more intuitive, but using a fixed-size array (for the 26 lowercase letters) is more efficient and allows the matches optimization.