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 a substring of s2.

The step-through player is coming for this one. Two Sum has the full animation today; the rest are being authored in the admin.

Pythontime O(n) · space O(1)

def checkInclusion(s1: str, s2: str) -> bool:
    if len(s1) > len(s2): return False
    cnt1, cnt2 = [0]*26, [0]*26
    for c in s1: cnt1[ord(c)-97] += 1
    for i in range(len(s2)):
        cnt2[ord(s2[i])-97] += 1
        if i >= len(s1): cnt2[ord(s2[i-len(s1)])-97] -= 1
        if cnt1 == cnt2: return True
    return False

Two Sum is free. Enroll to unlock every visualization and save where you stopped.Enroll free

Watch the video walkthrough