class Solution:
    def checkInclusion(self, s1: str, s2: str) -> bool:
        # How to solve it: Sliding window.
        # Create a dict count of s1.  This is the target.
        # Have two pointers in s2.  Advance the left pointer until you find a
        # character that is in the s1 dict.  Then start advancing the right pointer.
        # As you advance the right pointer, add to a dict
        # count of the characters in the current window in s2.  Also have a variable
        # 'required_matches_remaining' that contains the number of characters in s1
        # that need to have their exact counts matched in the current window in s2.
        # When you add a new character to the s2 dict, compare its count to the s1 dict,
        # and if the count is switching to exactly correct, decrement the
        # required_matches variable; if the count is switching from exactly correct to
        # too much, this won't be a permutation and you need to start advancing the left
        # pointer again.  If the right pointer hits a character not in the s1 dict, you
        # need to start advancing the left pointer again.
 
        # Fill out the s1 (target) dict:
        s1_dict = dict()
        for char in s1:
            if char not in s1_dict:
                s1_dict[char] = 1
            else:
                s1_dict[char] += 1
        
        s2_dict = defaultdict(int)
        l = 0
        # We want to keep going as long as the left pointer is suitably far from the end
        while l <= len(s2) - len(s1):
            # If the character isn't even in the s1 dict, don't bother doing anything
            if s2[l] not in s1_dict:
                pass
            else:
                r = l
                remaining_characters_to_match = len(s1_dict.keys())
                while r <= len(s2):
                    if remaining_characters_to_match == 0:
                        return True
                    
                    char = s2[r]
                    s2_dict[char] += 1
                    if char not in s1_dict or s2_dict[char] > s1_dict[char]:
                        break
                    elif s2_dict[char] == s1_dict[char]:
                        remaining_characters_to_match -= 1
                    r += 1

            s2_dict.clear()
            l += 1
        
        # If we haven't found a suitable substring by now, return False
        return False