567. Permutation in String

Problem Description

Given two strings s1 and s2, determine if s2 contains a permutation of s1. A permutation of a string is another string with the same characters, but in a possibly different order.

Example 1:

s1 = "ab", s2 = "eidbaooo" => true ("ba" is a permutation of "ab")

Example 2:

s1 = "ab", s2 = "eidboaoo" => false

Solution: Sliding Window

This problem can be efficiently solved using a sliding window approach. We'll maintain a window of the same size as s1 and slide it across s2. For each window, we check if it contains a permutation of s1.

Algorithm:

1. Character Counts: Create a frequency map (e.g., using a hash map or array) to store the character counts of s1. We'll call this s1_counts.

2. Sliding Window: Initialize a sliding window of size len(s1) on s2. Create a second frequency map window_counts to track character counts within the current window.

3. Iteration: Iterate through s2.

   • Add character: Add the current character to window_counts.
   • Remove character: If the window has grown beyond len(s1), remove the leftmost character from window_counts.
   • Comparison: Compare window_counts and s1_counts. If they are identical, we've found a permutation of s1 within s2, and we return true.

4. No Permutation: If the loop completes without finding a match, return false.

Code Implementation (Python)

from collections import Counter
 
def checkInclusion(s1, s2):
    """
    Checks if s2 contains a permutation of s1 using a sliding window.
 
    Args:
        s1: The string to search for permutations of.
        s2: The string to search within.
 
    Returns:
        True if s2 contains a permutation of s1, False otherwise.
    """
    n1 = len(s1)
    n2 = len(s2)
 
    if n1 > n2:  # Optimization: s1 can't be a substring if it's longer
        return False
 
    s1_counts = Counter(s1)
    window_counts = Counter()
 
    for i in range(n2):
        window_counts[s2[i]] += 1
 
        if i >= n1:  # Remove leftmost character from window
            if window_counts[s2[i - n1]] == 1:
                del window_counts[s2[i - n1]]
            else:
                window_counts[s2[i - n1]] -= 1
 
        if window_counts == s1_counts:
            return True
 
    return False
 

Time and Space Complexity

• Time Complexity: O(n), where n is the length of s2. We iterate through s2 once. The operations within the loop (adding/removing from counters) are O(1) on average for hash maps.

• Space Complexity: O(1). The space used by the frequency maps is constant because the number of unique characters is limited to the 26 lowercase English letters (or the size of your character set).

Code in Other Languages

The same algorithm can be implemented efficiently in other programming languages. The key is using an appropriate data structure for efficient character counting (e.g., arrays for ASCII characters, hash maps for larger character sets). Examples in other languages would follow the same algorithmic structure with minor syntax changes. (See the original response for examples in Java, C++, Go, TypeScript, Rust, C#, and PHP).