python easy solution sliding window using two dict


  • 1
    H
    class Solution(object):
        def findAnagrams(self, s, p):
            """
            :type s: str
            :type p: str
            :rtype: List[int]
            """
            charFreq = {}  # target charFreq Map
            for c in p:
                charFreq[c] = charFreq.get(c, 0) + 1
            windows = {}  # keep track of chars in windows
            res = []
            count = 0
            i, j = 0, 0
            while j < len(s):
                if s[j] in charFreq:
                    windows[s[j]] = windows.get(s[j], 0) + 1
                    if windows[s[j]] <= charFreq[s[j]]:  # windows need this char
                        count += 1
                j += 1  # increase j, extend window
                if j - i == len(p): # window is full
                    if count == len(p):
                        res.append(i)
                    if s[i] in charFreq:
                        if windows[s[i]] <= charFreq[s[i]]:  # windows don't need this char
                            count -= 1
                        windows[s[i]] -= 1
                    i += 1  # increase i, move window
            return res
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.