# Todo algoritmo de sliding window se beneficia do uso de uma estrutura de auxiliar
# de processamento para evitar reprocessar elementos já vistos.
#
# A cada movimento da janela, é necessário atualizar essa estrutura auxiliar:
# - em função das mudanças no lado direito da janela (quem entra)
# - em função das mudanças no lado esquerdo da janela (quem sai)
#
# No problema a seguir, a estrutura auxiliar é um contador, contendo as frequências dos
# elementos presentes na janela atual.
#
# Caso a contagem de elementos da janela atual seja igual à do padrão buscado, temos um anagrama.

from collections import Counter

class Solution:
    def findAnagrams(self, s, p):
        # Processando entradas inválidas
        if len(s) < len(p):
            return []

        # Criando a estrutura auxiliar de processamento
        freq_p = Counter(p)
        freq_window = Counter(s[:len(p)])

        # Deslizando a janela e atualizando a estrutura auxiliar de processamento
        ocorrencias = []
        i = 0
        while True:
            # Conferindo se a janela atual é um anagrama
            if freq_p == freq_window:
                ocorrencias.append(i)

            # Testando a condição de término do laço
            if i + 1 > len(s) - len(p):
                break

            # Atualizando a estrutura auxiliar de processamento em função do caracter que sai
            freq_window[s[i]] -= 1
            if not freq_window[s[i]]:
                del freq_window[s[i]]

            # Atualizando a estrutura auxiliar de processamento em função do caracter que entra
            freq_window[s[i+len(p)]] += 1

            # Deslocando a janela
            i += 1
        return ocorrencias