567. Permutation in String

Problem Link

We use a sliding window with two pointers \(l\) and \(r\) the current substring (in \(s2\)). The window will represent substring only consisting characters from \(s1\). This way when our window reaches length of \(s1\), we can say we've found the permutation. To grow/shrink our window, we need a hashmap storing frequency of \(s1\). We'll use this map to consume characters as our window grow, and when the frequency reaches \(\lt 0\), we can shrink the window. At any point, if \(r-l+1 == len(s)\), we've found the permutation of \(s1\).

Runtime Complexity

Time: O(n); each character is only processed once

Space: O(1); constant space as only english letters used as keys in hashmap

PythonGo

class Solution:
    def checkInclusion(self, s1: str, s2: str) -> bool:
        counts = Counter(s1)
        l = 0
        for r, ch in enumerate(s2):
            counts[ch] -= 1
            while counts[ch] < 0:
                counts[s2[l]] += 1
                l += 1

            if r - l + 1 == len(s1):
                return True
        return False

func checkInclusion(s1 string, s2 string) bool {
    counts := make(map[rune]int)
    for _, ch := range s1 {
        counts[ch]++
    }
    var l int
    for r, ch := range s2 {
        counts[ch]--
        for counts[ch] < 0 {
            counts[rune(s2[l])]++
            l++
        }
        if r-l+1 == len(s1) {
            return true
        }
    }
    return false
}

---