LC567. Permutation in String

Approach 1: Using two counters

class Solution:
    def checkInclusion(self, s1: str, s2: str) -> bool:
        if len(s1) > len(s2):
            return False
        
        if len(s1) == len(s2) and Counter(s1) == Counter(s2):
            return True
 
        if len(s1) == 1:
            return s1 in s2
        
        s1Counts = Counter(s1)
        windowCounts = Counter(s2[:len(s1) - 1])
 
        for l in range(len(s2) - len(s1) + 1):
            r = l + len(s1) - 1
 
            windowCounts[s2[r]] += 1
 
            if s1Counts == windowCounts:
                return True
            
            windowCounts[s2[l]] -= 1
 
        return False

Complexity

Time: $O(26\cdot n)\approx O(n)$
Space: $O(1)$

Approach 2: Tracking total matches

import string
from collections import Counter
 
class Solution:
    def checkInclusion(self, s1: str, s2: str) -> bool:
        if len(s1) > len(s2): return False
 
        matches = 0
        s1Counts = Counter(s1)
        s2Counts = Counter(s2[:len(s1) - 1])
 
        for c in string.ascii_lowercase:
            matches += int(s1Counts[c] == s2Counts[c])
        
        for l in range(0, len(s2) - len(s1) + 1):
            r = l + len(s1) - 1
            lc, rc = s2[l], s2[r]
 
            s2Counts[rc] += 1
            # Increment matches if post sliding, right char
            # counts are matching. Else, see if before sliding,
            # right char counts were matching. If so, we lost a match
            # post sliding.
            if s1Counts[rc] == s2Counts[rc]:
                matches += 1
            elif s1Counts[rc] == s2Counts[rc] - 1:
                matches -= 1
            
            if matches == 26:
                return True
            
            s2Counts[lc] -= 1
            # Increment matches if post sliding, left char
            # counts are matching. Else, see if before sliding,
            # left char counts were matching. If so, we lost a match
            # post sliding.
            if s1Counts[lc] == s2Counts[lc]:
                matches += 1
            elif s1Counts[lc] == s2Counts[lc] + 1:
                matches -= 1
 
        return False

Complexity

Time: $O(n)$
Space: $O(1)$

Other Languages