Solutions

# Brute force (nested loop and sorting), or sliding window using letter frequency arrays of window and s1.
# sliding-window

# Brute force - O(n^3 logn) time, O(1) space
def checkInclusion(s1: str, s2: str) -> bool:
    if len(s1) > len(s2):
        return False

    for i in range(len(s2) - len(s1) + 1):
        if sorted(s2[i:i+len(s1)]) == sorted(s1):
            return True
    return False

# Sliding window - O(n) time, O(1) space
def checkInclusion(s1: str, s2: str) -> bool:
    if len(s1) > len(s2):
        return False

    # Get the frequency array of s1
    s1_freq = [0] * 26
    for l in s1:
        s1_freq[ord(l) - ord('a')] += 1

    # Populate the frequency array of first window of len(s1)
    wfreq = [0] * 26
    for i in range(len(s1)):
        letter = s2[i]
        wfreq[ord(letter) - ord('a')] += 1

    l = 0
    for r in range(len(s1), len(s2)):
        # Check if windows frequency array is the same as s1 frequency array - O(1)
        same = True
        for i in range(26):
            if wfreq[i] != s1_freq[i]:
                same = False
                break

        if same:
            return True
        
        # Increment r and increase its corresponding entry in wfreq
        wfreq[ord(s2[r]) - ord('a')] += 1

        # Increment l and decrease its corresponding entry in wfreq
        wfreq[ord(s2[l]) - ord('a')] -= 1
        l += 1

    # Check if the final window frequency array is the same as s1 frequency array
    return all([wf == s1f for wf, s1f in zip(wfreq, s1_freq)])