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.

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

My Idea

The idea here was to set a window size of len(s1) and check the frequency hashmap of the characters in the window of s2 against the one for s1.

My solution

#Time Complexity: O(n1*n2)
def checkInclusion(s1:str, s2:str) -> bool:
    l = 0
    maxL = len(s1)
    d1 = dict()
    d2 = dict()
    for c in s1:
        d1[c]=1+d1.get(c,0)
    for r in range(len(s2)):
        d2[s2[r]]=1+d2.get(s2[r],0)

        if r-l+1 < maxL:
            continue
        elif r-l+1 > maxL:
            d2[s2[l]]-=1
            if d2[s2[l]]==0:
                del d2[s2[l]]
            l+=1
        if d1==d2:
            return True
    return False