algoadvance

Given two strings s1 and s2, return true if s2 contains a permutation of s1, or false otherwise.

In other words, 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:

Clarifying Questions

  1. What constitutes a permutation?
    • A permutation of a string is another string that contains the same characters, only the order of characters can be different.
  2. Can s1 be longer than s2?
    • No, since a permutation of s1 would not fit in s2 if s1 is longer than s2.
  3. What if both s1 and s2 are empty?
    • This is not possible as per the constraints 1 <= s1.length, s2.length.

Strategy

To determine if any permutation of s1 is a substring of s2, we can use the sliding window technique along with character frequency counts:

  1. Character Count Matching:
    • Count the frequency of each character in s1.
    • Maintain a sliding window of the same length as s1 and count the frequency of characters in this window within s2.
  2. Sliding Window:
    • Slide the window over s2 and compare the frequency count of the current window to the frequency count of s1.
    • If they match at any point, return true.
    • If the window reaches the end of s2 without a match, return false.
  3. Efficiency:
    • Because each position in s2 is processed a constant number of times, the time complexity should be linear, (O(N)), where (N) is the length of s2.

Code

Let’s implement the described approach:

def checkInclusion(s1: str, s2: str) -> bool:
    from collections import Counter
    
    len1, len2 = len(s1), len(s2)
    
    if len1 > len2:
        return False
    
    s1_count = Counter(s1)
    window_count = Counter(s2[:len1])
    
    if s1_count == window_count:
        return True
    
    for i in range(len1, len2):
        window_count[s2[i]] += 1
        window_count[s2[i - len1]] -= 1
        
        if window_count[s2[i - len1]] == 0:
            del window_count[s2[i - len1]]
        
        if s1_count == window_count:
            return True
    
    return False

Time Complexity

By following this strategy and implementing the sliding window approach, we ensure an efficient solution to the problem.

Try our interview co-pilot at AlgoAdvance.com