LeetCode: 30. Substring with Concatenation of All Words

O(NK)...

from collections import deque, defaultdict

class Solution:
    def findSubstring(self, s: str, words: List[str]) -> List[int]:
        n = len(s)
        m = len(words)
        len_words = len(words[0])
        if n < m * len_words:
            return []
        
        ret = set()
        
        ans = defaultdict(int)
        for word in words:
            ans[word] += 1
        
        words = set(words)
        
        for i in range(0, len_words):
            comp = defaultdict(int)
            q = deque([], maxlen=m)
            while i <= n - len_words:
                cur = s[i:i+len_words]
                if len(q) == m:
                    popped = q.popleft()
                    if popped in words:
                        comp[popped] -= 1
                q.append(cur)           
                if cur in words:
                    comp[cur] += 1
                    if comp == ans:
                        ret.add(i-len_words*(m-1))
                i += len_words

        return list(ret)