30. Substring with Concatenation of All Words

from collections import Counter

class Solution:
    def findSubstring(self, s: str, words: list[str]) -> list[int]:
        if not s or not words:
            return []

        word_len = len(words[0])
        word_count = len(words)
        total_len = word_len * word_count

        if len(s) < total_len:
            return []

        need = Counter(words)
        ans = []
        for offset in range(word_len):
            left = offset
            right = offset
            count = 0
            window = Counter()

            while right + word_len <= len(s):
                word = s[right:right + word_len]
                right += word_len
                if word not in need:
                    window.clear()
                    count = 0
                    left = right
                    continue

                window[word] += 1
                count += 1

                while window[word] > need[word]:
                    removed = s[left:left + word_len]
                    window[removed] -= 1
                    left += word_len
                    count -= 1

                if count == word_count:
                    ans.append(left)

                    removed = s[left:left + word_len]
                    window[removed] -= 1
                    left += word_len
                    count -= 1

        return ans