24 de Março
Maior substring sem caracteres repetidos
Como perceber que o problema pede uma janela que expande e contrai, não um recomeco completo a cada repetição.
Janela Deslizante Intermediario 20 min TypeScript
Dada uma string s, retorne o comprimento da maior substring sem caracteres repetidos.
Exemplo:
Input: s = "abcabcbb"
Output: 3
A maior substring sem repetição e "abc", com comprimento 3.
O que perceber antes de codar
- O problema pede substring, não subsequencia.
- A resposta e um comprimento, não precisa retornar a substring em si.
- Repetição inválida a janela atual, mas não significa recomecar do zero.
Erros comuns
- confundir substring com subsequencia
- resetar toda a janela ao ver repetição e perder trabalho já feito
Passo 1 — Entender o que inválida a substring
Enquanto todos os caracteres forem unicos, a janela atual continua valida.
O problema começa quando aparece uma repetição.
A pergunta não e "qual substring testar agora?".
A pergunta e:
como manter uma janela valida enquanto ando pela string?
Passo 2 — Escrever a versão inicial correta
Uma versão inicial boa e fixar um início e estender o fim até repetir:
export function lengthOfLongestSubstring(s: string): number {
let best = 0
for (let start = 0; start < s.length; start += 1) {
const seen = new Set<string>()
for (let end = start; end < s.length; end += 1) {
const char = s[end]
if (seen.has(char)) {
break
}
seen.add(char)
best = Math.max(best, end - start + 1)
}
}
return best
}
Funciona. Mas recomeça trabalho demais para cada início.
Passo 3 — Perguntar o que realmente precisa sair da janela
Se right encontrou um caractere repetido, precisa limpar tudo?
Não.
Só precisa remover da esquerda até aquele caractere deixar de estar duplicado.
Isso e o coracao de uma janela deslizante.
Passo 4 — Expandir e contrair sob regra
Use:
rightpara expandirleftpara contrair quando a regra quebraconjunto hashpara representar os caracteres dentro da janela atual
A janela só anda para frente. Não precisa voltar.
O editor interativo precisa de JavaScript. Voce ainda pode ler o desafio e copiar o codigo inicial abaixo.
Codigo inicial
export function lengthOfLongestSubstring(s: string): number {
// sua solução aqui
return 0
}
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(min(n, charset))
Solução 1 — Testar cada início
Boa versão inicial para enxergar a regra.
export function lengthOfLongestSubstring(s: string): number {
let best = 0
for (let start = 0; start < s.length; start += 1) {
const seen = new Set<string>()
for (let end = start; end < s.length; end += 1) {
const char = s[end]
if (seen.has(char)) {
break
}
seen.add(char)
best = Math.max(best, end - start + 1)
}
}
return best
}Solução 2 — Janela deslizante com conjunto hash em O(n)
Agora a janela se ajusta sem recomecar tudo.
export function lengthOfLongestSubstring(s: string): number {
const window = new Set<string>()
let left = 0
let best = 0
for (let right = 0; right < s.length; right += 1) {
const char = s[right]
while (window.has(char)) {
window.delete(s[left])
left += 1
}
window.add(char)
best = Math.max(best, right - left + 1)
}
return best
}Cada caractere entra e sai da janela no máximo uma vez.
O que dizer na entrevista
Uma explicação curta e boa seria:
A versão inicial testa cada início e custa
O(n²). A versão otimizada mantem uma janela sem repetição. Eu expando comrighte, quando aparece duplicata, contraio comleftsó o necessário até a janela voltar a ficar valida. Isso reduz paraO(n).
Isso mostra que você:
- entendeu a regra que inválida a janela
- explicou a janela deslizante como movimento controlado
- evitou tratar a otimização como template cego
Quando esse padrão aparece de novo
Esse padrão reaparece quando você precisa:
- manter uma janela valida
- expandir enquanto a regra vale
- contrair até corrigir violacao
- contar ou maximizar algo dentro de um intervalo movel
O ponto não e decorar que
janela deslizantee igual adois ponteiros.
O ponto e perceber quando o problema fala de uma faixa contigua com regra local.