Algoritmo 14 — Sliding Window — Mininum Window Substring

Sumário

• Apresentação do problema
• Solução
• Conclusão

Apresentação do problema

Dadas duas strings s e t de comprimentos m e n respectivamente, retorne a menor substring contínua de s de modo que cada caractere de t (incluindo duplicatas) esteja incluído na janela. Se não houver tal substring, retorne a string vazia “”.

O objetivo é identificar essa substring de forma eficiente, de modo que todas as letras de t estejam presentes na substring escolhida de s, incluindo repetições, caso tenha. Sliding window é um método que permite percorrer a string s, expandindo e contraindo uma janela de caracteres, para ajustar dinamicamente a porção de s sendo considerada, sempre buscando minimizar o tamanho dessa janela enquanto ainda satisfaz a condição de incluir todos os caracteres de t.

Solução

func minWindow(s string, t string) string {
   start, end := 0, 0
   targetCharacterFrequency := make(map[uint8]int)
   currentCharacterFrequency := make(map[uint8]int)
   distinctCharacterCount := 0
   minSubstring := ""
  
   for index := range t {
      targetCharacterFrequency[t[index]]++
   }
  
   for end < len(s) {
      currentCharacterFrequency[s[end]]++
      if targetCharacterFrequency[s[end]] != 0 &&
         targetCharacterFrequency[s[end]] == currentCharacterFrequency[s[end]] {
         distinctCharacterCount++
      }
    
      for distinctCharacterCount == len(targetCharacterFrequency) {
         if minSubstring == "" {
            minSubstring = s[start:end+1]
         }
         if end - start + 1 < len(minSubstring) {
            minSubstring = s[start:end+1]
         }
      
         currentCharacterFrequency[s[start]]--
         if currentCharacterFrequency[s[start]] < targetCharacterFrequency[s[start]] {
            distinctCharacterCount--
         }
      
         start++
      }
      end++
   }
  
   return minSubstring
}

Utilizamos duas principais estruturas de dados, ambas sendo mapas, para rastrear as frequências dos caracteres. targetCharacterFrequency mapeia cada caractere em t para sua frequência, indicando quantas vezes cada caractere deve aparecer na substring para satisfazer a condição. currentCharacterFrequency mapeia os caracteres dentro da janela atual em s para suas frequências, facilitando a verificação de se a janela atual contém todos os caracteres necessários de t.

O algoritmo começa inicializando variáveis para marcar o início e o fim da janela de exploração (start e end), um contador (distinctCharacterCount) para rastrear quantos caracteres únicos de t foram completamente cobertos pela janela atual, e uma string (minSubstring) para armazenar a menor substring encontrada.

O loop principal do código expande aos poucos a janela movendo end ao longo de s. Para cada novo caractere incluído na janela (indicado pelo índice end), o algoritmo atualiza currentCharacterFrequency e verifica se esse caractere contribui para a cobertura completa dos caracteres de t. Quando um caractere de t é totalmente coberto pela janela atual (ou seja, a frequência do caractere na janela é igual ou maior que sua frequência alvo em t), distinctCharacterCount é incrementado.

Quando distinctCharacterCount iguala o número de caracteres únicos em t, significando que a janela atual contém todos os caracteres necessários de t pelo menos uma vez, o algoritmo tenta encolher a janela para encontrar a menor substring possível que ainda satisfaz a condição. Isso é feito movendo start para a direita, reduzindo a janela pelo início enquanto ainda contém todos os caracteres necessários. Se a condição deixa de ser verdadeira (ou seja, a frequência de um caractere necessário cai abaixo de seu alvo), distinctCharacterCount é decrementado, e o processo de tentativa de encolher a janela cessa.

Durante cada tentativa de encolhimento da janela, verificamos se a substring atual é menor que minSubstring (ou se minSubstring ainda não foi definida) e, em caso afirmativo, atualiza minSubstring com a substring atual. Esse processo de expansão e contração continua até end percorrer toda a string s.

Por fim, minSubstring contém a menor substring de s que inclui todos os caracteres de t, ou permanece vazia se tal substring não existir, sendo então retornada como resultado. Esse método equilibra a necessidade de cobrir todos os caracteres necessários com o objetivo de minimizar o tamanho da substring, mostrando uma aplicação prática do padrão de sliding window em problemas de strings.

Conclusão

Nossa solução permite analisar a string de entrada de maneira linear, ou seja, cada caractere de `s` é visitado uma vez ao expandir a janela e, potencialmente, mais uma vez ao contrair a janela, resultando em uma complexidade de tempo aproximadamente O(2n) em cenários piores, onde n é o comprimento de s. Isso é considerado eficiente, pois a abordagem evita a necessidade de revisitar múltiplas substrings de maneira excessiva.

Do ponto de vista de memória, o algoritmo utiliza estruturas de dados adicionais (dois mapas) cujos tamanhos dependem do número de caracteres distintos em t e s. Embora isso introduza um custo de memória adicional, este custo é geralmente limitado pela pequena quantidade de caracteres únicos possíveis (especialmente se considerarmos apenas o alfabeto ASCII). Portanto, a utilização de memória pode ser considerada moderada.

Redigido por Eliabe Bastos, revisado por Gabriel Palitot