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 "ba" which is a permutation of s1

Example 2:

Input: s1 = "ab", s2 = "eidboaoo"
Output: false

Approach: Sliding Window with Frequency Count (Optimal)

Intuition

A permutation means the characters are the same, just in different order. So we need to find a substring in s2 that has the exact same character frequencies as s1.

Use a sliding window of size len(s1) and compare character frequencies.

Key Insight

• Create frequency map for s1
• Slide a window of size len(s1) through s2
• At each position, check if window frequencies match s1 frequencies
• Optimization: Instead of comparing entire maps, track number of matching characters

Algorithm

def checkInclusion(s1, s2):
    if len(s1) > len(s2):
        return False
    
    s1_count = {}
    s2_count = {}
    
    # Count characters in s1
    for c in s1:
        s1_count[c] = s1_count.get(c, 0) + 1
    
    # Initial window in s2
    for i in range(len(s1)):
        s2_count[s2[i]] = s2_count.get(s2[i], 0) + 1
    
    # Check initial window
    if s1_count == s2_count:
        return True
    
    # Slide window
    for i in range(len(s1), len(s2)):
        # Add new character
        s2_count[s2[i]] = s2_count.get(s2[i], 0) + 1
        
        # Remove old character
        left_char = s2[i - len(s1)]
        s2_count[left_char] -= 1
        if s2_count[left_char] == 0:
            del s2_count[left_char]
        
        # Check if match
        if s1_count == s2_count:
            return True
    
    return False

Example Walkthrough

For s1 = "ab", s2 = "eidbaooo":

s1_count = {a:1, b:1}

Window "ei": {e:1, i:1} ✗
Window "id": {i:1, d:1} ✗
Window "db": {d:1, b:1} ✗
Window "ba": {b:1, a:1} ✓ MATCH!

Time Complexity

• O(n): Single pass through s2, where n = len(s2)
• Map comparison is O(26) = O(1) for lowercase letters

Space Complexity

• O(1): At most 26 characters in maps

Optimized Approach: Match Counter

Instead of comparing maps, count how many characters have matching frequencies.

def checkInclusion(s1, s2):
    if len(s1) > len(s2):
        return False
    
    s1_count = [0] * 26
    s2_count = [0] * 26
    
    for c in s1:
        s1_count[ord(c) - ord('a')] += 1
    
    matches = 0
    for i in range(26):
        if s1_count[i] == s2_count[i]:
            matches += 1
    
    for i in range(len(s2)):
        if matches == 26:
            return True
        
        # Add right character
        idx = ord(s2[i]) - ord('a')
        s2_count[idx] += 1
        if s2_count[idx] == s1_count[idx]:
            matches += 1
        elif s2_count[idx] == s1_count[idx] + 1:
            matches -= 1
        
        # Remove left character
        if i >= len(s1):
            idx = ord(s2[i - len(s1)]) - ord('a')
            s2_count[idx] -= 1
            if s2_count[idx] == s1_count[idx]:
                matches += 1
            elif s2_count[idx] == s1_count[idx] - 1:
                matches -= 1
    
    return matches == 26

Same complexity, but avoids repeated map comparisons.