We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Permutation in String

Difficulty: Medium

Problem Description

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.

Key Insights

  • A permutation of s1 has the same characters with the same frequency.
  • We can use a sliding window approach to check every substring of s2 that has the same length as s1.
  • A frequency count (using a hash table) can help us quickly compare character counts between s1 and the current window in s2.

Space and Time Complexity

Time Complexity: O(n), where n is the length of s2.
Space Complexity: O(1), since the hash table size is fixed (26 lowercase English letters).

Solution

To solve the problem, we can use the sliding window technique alongside a hash table (or array) to count character frequencies. We will maintain a frequency count for s1 and compare it with the frequency count of the current window in s2. If they match at any point, it indicates that a permutation of s1 exists as a substring in s2.

Code Solutions

def checkInclusion(s1: str, s2: str) -> bool:
    from collections import Counter

    s1_count = Counter(s1)  # Frequency count of s1
    window_count = Counter()  # Frequency count for the current window in s2
    s1_length = len(s1)
    
    for i in range(len(s2)):
        window_count[s2[i]] += 1  # Add the new character to the window
        
        # Remove the leftmost character if the window exceeds the size of s1
        if i >= s1_length:
            left_char = s2[i - s1_length]
            if window_count[left_char] == 1:
                del window_count[left_char]
            else:
                window_count[left_char] -= 1
        
        # Compare the frequency counts
        if window_count == s1_count:
            return True
            
    return False
← Back to All Questions