Minimum Window Substring

O Minimum Window Substring é um problema clássico de sliding window em que o objetivo é encontrar a menor substring contínua de uma string s que contenha todos os caracteres de outra string t (respeitando multiplicidade).

---

Enunciado (forma comum)

Dadas duas strings s e t, retorne a menor substring de s que contenha todos os caracteres de t. Se não existir, retorne string vazia.

Exemplo

• s = "ADOBECODEBANC"
• t = "ABC"
• Resultado: "BANC"

---

Diferença para “Longest Substring Without Repeating Characters”

• Longest: manter a janela válida o máximo possível.
• Minimum Window: manter a janela válida e o menor possível.
• Aqui há contagem de caracteres (frequência), não apenas presença/ausência.

---

Ideia central

Usa-se sliding window com dois mapas de frequência:

• need: contagem dos caracteres exigidos por t
• window: contagem dos caracteres atuais da janela em s

Além disso, controlamos:

• required: número de caracteres distintos em t
• formed: quantos desses caracteres já estão satisfeitos na janela

A janela é:

• expandida para a direita até ficar válida
• contraída pela esquerda para minimizar o tamanho

---

Algoritmo (passo a passo)

1. Conte os caracteres de t em need

2. Inicialize:

   • left = 0
   • formed = 0
   • window = {}
   • best = (início, tamanho) com tamanho infinito

3. Percorra s com right:

   • Adicione s[right] a window
   • Se window[c] == need[c], incremente formed

4. Enquanto formed == required:

   • Atualize a melhor resposta
   • Tente contrair a janela movendo left
   • Se remover um caractere quebra a condição, decrementa formed

5. Retorne a substring correspondente à melhor janela

---

Implementação em Python

from collections import Counter, defaultdict
 
def minWindow(s: str, t: str) -> str:
    if not t or not s:
        return ""
 
    need = Counter(t)
    window = defaultdict(int)
 
    required = len(need)
    formed = 0
 
    left = 0
    best_len = float("inf")
    best_l = 0
 
    for right, c in enumerate(s):
        window[c] += 1
 
        if c in need and window[c] == need[c]:
            formed += 1
 
        while formed == required:
            if right - left + 1 < best_len:
                best_len = right - left + 1
                best_l = left
 
            left_char = s[left]
            window[left_char] -= 1
 
            if left_char in need and window[left_char] < need[left_char]:
                formed -= 1
 
            left += 1
 
    return "" if best_len == float("inf") else s[best_l:best_l + best_len]

---

Exemplo resumido ("ADOBECODEBANC", "ABC")

• Expande até conter A, B, C
• Quando válido, começa a contrair
• Continua expandindo/contraindo
• Melhor janela encontrada: "BANC"

---

Complexidade

• Tempo: O(|s| + |t|) Cada ponteiro (left, right) percorre s no máximo uma vez.
• Espaço: O(|t|) Mapas de frequência baseados nos caracteres exigidos.

---

Pontos-chave que costumam confundir

• formed conta caracteres satisfeitos, não o total de caracteres.
• Frequência importa ("AABC" ≠ "ABC").
• A contração da janela é onde a resposta mínima é encontrada.

---

Padrão de entrevista

Esse problema é o exemplo canônico de:

• Sliding Window com frequência
• Dois ponteiros + mapas
• Expansão para validar, contração para otimizar