24 de Março
Menor janela contendo tudo
Como transformar "contem tudo?" em uma condição de satisfação e contrair a janela só enquanto ela continua valida.
Janela Deslizante Avancado 30 min TypeScript
Dadas duas strings s e t, retorne a menor substring de s que contenha todos os caracteres de t, incluindo repetições.
Se não existir substring valida, retorne "".
Aqui no SeniorPath, em caso de empate de tamanho, retorne a que aparece primeiro.
Exemplo:
Input: s = "ADOBECODEBANC", t = "ABC"
Output: "BANC"
O que perceber antes de codar
- O problema pede substring, entao a resposta precisa ser contigua.
- Não basta conter os caracteres. Também precisa respeitar as quantidades pedidas por `t`.
- A parte difícil não e expandir. E saber quando a janela já satisfaz tudo e quanto ela pode encolher.
Erros comuns
- tratar a janela como valida só por conter os tipos de caractere, ignorando frequência
- continuar expandindo mesmo depois que a janela já satisfaz tudo e perder a chance de minimizar
Passo 1 - Entender o que significa "conter tudo"
Se t = "ABC", a janela precisa conter:
- pelo menos um
A - pelo menos um
B - pelo menos um
C
Se t = "AABC", a regra muda:
- dois
A - um
B - um
C
Entao a pergunta certa não e só "esse caractere existe?".
A pergunta e:
- a janela atual já bateu todas as frequencias exigidas?
Passo 2 - Escrever a versão inicial mais direta
A versão inicial natural e:
- fixar um início
- expandir o fim
- quando a janela ficar valida, atualizar a melhor resposta
Funciona.
Mas recomeca trabalho demais para cada início.
Passo 3 - Descobrir a regra de satisfação
Monte um mapa need com as frequencias de t.
Depois, enquanto expande a janela, mantenha um mapa window.
A janela só fica valida quando, para cada caractere exigido, window[char] >= need[char].
Uma forma boa de controlar isso e contar quantos tipos de caractere já atingiram a frequência exigida.
Passo 4 - Expandir até satisfazer e contrair até violar
Esse e o coracao do problema:
rightexpande a janela- quando ela satisfaz tudo,
leftcontrai - enquanto continuar valida, tente encolher
A melhor janela nasce justamente nessa fase de contracao.
O editor interativo precisa de JavaScript. Voce ainda pode ler o desafio e copiar o codigo inicial abaixo.
Codigo inicial
export function minWindow(s: string, t: string): string {
// sua solução aqui
return ""
}
Ainda não resolveu?
Ver a solução agora pode reduzir o aprendizado. Vale a pena tentar mais um pouco.
Abrir a solucao de referencia
Sem JavaScript, a solucao de referencia aparece inline em vez de um dialogo.
Solução
Complexidade final
Tempo: O(n)
Espaço: O(charset)
Solução 1 - Testar cada início e expandir até valer
Boa versão inicial para deixar visível a regra de validade.
function coversAll(window: Map<string, number>, need: Map<string, number>): boolean {
for (const [char, amount] of need.entries()) {
if ((window.get(char) ?? 0) < amount) {
return false
}
}
return true
}
export function minWindow(s: string, t: string): string {
const need = new Map<string, number>()
for (const char of t) {
need.set(char, (need.get(char) ?? 0) + 1)
}
let best = ""
for (let start = 0; start < s.length; start += 1) {
const window = new Map<string, number>()
for (let end = start; end < s.length; end += 1) {
const char = s[end]
window.set(char, (window.get(char) ?? 0) + 1)
if (coversAll(window, need)) {
const candidate = s.slice(start, end + 1)
if (best === "" || candidate.length < best.length) {
best = candidate
}
break
}
}
}
return best
}Funciona, mas refaz muita contagem para cada novo início.
Solução 2 - Janela deslizante com mapas hash e satisfação em O(n)
Agora a janela anda de forma incremental.
export function minWindow(s: string, t: string): string {
if (t.length === 0 || s.length < t.length) {
return ""
}
const need = new Map<string, number>()
for (const char of t) {
need.set(char, (need.get(char) ?? 0) + 1)
}
const window = new Map<string, number>()
const requiredKinds = need.size
let satisfiedKinds = 0
let left = 0
let bestStart = -1
let bestLength = Infinity
for (let right = 0; right < s.length; right += 1) {
const rightChar = s[right]
window.set(rightChar, (window.get(rightChar) ?? 0) + 1)
if (need.has(rightChar) && window.get(rightChar) === need.get(rightChar)) {
satisfiedKinds += 1
}
while (satisfiedKinds === requiredKinds) {
const currentLength = right - left + 1
if (currentLength < bestLength || (currentLength === bestLength && left < bestStart)) {
bestStart = left
bestLength = currentLength
}
const leftChar = s[left]
window.set(leftChar, window.get(leftChar)! - 1)
if (need.has(leftChar) && window.get(leftChar)! < need.get(leftChar)!) {
satisfiedKinds -= 1
}
left += 1
}
}
if (bestStart === -1) {
return ""
}
return s.slice(bestStart, bestStart + bestLength)
}O insight forte aqui e separar duas fases da mesma janela:
- expandir até satisfazer
- contrair até quase quebrar
O que dizer na entrevista
Uma explicação curta e boa seria:
O problema não e só conter os caracteres de
t, mas também as frequencias. A versão inicial testa cada início e expande até achar uma janela valida. A versão forte usajanela deslizantecom dois mapas de contagem e um contador de quantos tipos já satisfizeram a frequência exigida. Quando a janela satisfaz tudo, eu contraio pela esquerda para tentar minimizar.
Isso mostra que você:
- entendeu a condição de validade real
- explicou por que a contracao existe
- tratou
janela deslizantecomo invariante, não como template
Quando esse padrão aparece de novo
Esse padrão reaparece quando você precisa:
- manter uma janela com contagem de frequência
- distinguir “tipos presentes” de “frequencias suficientes”
- expandir até satisfazer e contrair até violar
O ponto não e decorar esse problema.
O ponto e aprender a modelar satisfação de janela.