Q27: Permutation in String. - DSA Patterns (Multi-Lang)

In Simple Words: Fixed-size sliding window of length len(s1). Maintain letter frequency matching between s1 and current window in s2.

Time: $O(N)$ | Space: $O(26) = O(1)$

Multi-Language SolutionsPython 3 • JavaScript • TypeScript • Java • C++

Switch tabs or choose All

def checkInclusion(s1: str, s2: str) -> bool:
    if len(s1) > len(s2): return False
    c1, c2 = [0] * 26, [0] * 26
    for i in range(len(s1)):
        c1[ord(s1[i]) - ord('a')] += 1
        c2[ord(s2[i]) - ord('a')] += 1
    matches = sum(1 for i in range(26) if c1[i] == c2[i])
    for i in range(len(s1), len(s2)):
        if matches == 26: return True
        r = ord(s2[i]) - ord('a')
        c2[r] += 1
        if c2[r] == c1[r]: matches += 1
        elif c2[r] == c1[r] + 1: matches -= 1
        l = ord(s2[i - len(s1)]) - ord('a')
        c2[l] -= 1
        if c2[l] == c1[l]: matches += 1
        elif c2[l] == c1[l] - 1: matches -= 1
    return matches == 26