567. Permutation in String

[fockspaces]

sliding window + dictionary

use two dictionaries for maintaining the sliding window char_counts, comparing whether the current window of s2 have the same key, value pairs with the s1.

class Solution:
    def checkInclusion(self, s1: str, s2: str) -> bool:
        char_freq_1, char_freq_2 = {}, {}
        pt = 0
        for c in s1:
            char_freq_1[c] = char_freq_1.get(c, 0) + 1
        for i in range(len(s2)):
            char_freq_2[s2[i]] = char_freq_2.get(s2[i], 0) + 1
            while i - pt + 1 > len(s1):
                char_freq_2[s2[pt]] -= 1
                pt += 1
            if char_freq_1 == {key:value for key, value in char_freq_2.items() if value != 0}:
                return True
        return False

[fockspaces]

we can furthur compact the space and time for change data strcture from dict to list. having a list with 26 elements that record the alphabets occurance, we can compare them directly.

class Solution:
    def checkInclusion(self, s1: str, s2: str) -> bool:
        char_freq_1, char_freq_2 = [0] * 26, [0] * 26
        pt = 0
        for c in s1:
            char_freq_1[ord(c) - ord('a')] += 1 
        for i in range(len(s2)):
            char_freq_2[ord(s2[i]) - ord('a')] += 1
            while i - pt + 1 > len(s1):
                char_freq_2[ord(s2[pt]) - ord('a')] -= 1
                pt += 1
            if char_freq_1 == char_freq_2:
                return True
        return False

[fockspaces]

btw,

space: O(N) -> length of s1 and s2 time: O(N) -> only iterate through each elements in one-pass