Maior Substring sem Repetições
Acompanhe as últimas posições vistas em uma janela.
Maior Substring sem Repetições é uma aula grátis de Coding Interview Prep no CoddyKit. Esta é a aula 3 de 4. Você pode ler a aula completa abaixo gratuitamente — depois pratica ao vivo no navegador com um editor de código integrado e um tutor de IA 24/7. Faz parte do caminho de aprendizado de Coding Interview Prep, e seu progresso é sincronizado entre a web e o app CoddyKit. O curso de Coding Interview Prep inclui 4 aulas no total.
Um problema clássico de janela
Encontre a subcadeia mais longa sem caracteres repetidos. Esse é um exemplo famoso de janela deslizante que aparece em praticamente todo sistema de avaliação. 🔤
A armadilha da força bruta
Verificar cada subcadeia em busca de duplicatas custa cerca de O(n^2) ou mais. Para strings longas, isso é lento demais, então é necessária uma varredura mais inteligente.
Janela de caracteres únicos
Mantenha uma janela que contenha sempre caracteres distintos. Expanda-a pela direita e, quando surgir uma repetição, reduza-a pela esquerda até que ela desapareça.
Lembre-se das últimas posições
Armazene o último índice de cada caractere em um dicionário. Assim, você saberá instantaneamente onde uma repetição foi vista pela última vez durante a varredura.
last = {}
left = 0
best = 0Percorra cada caractere
Faça um laço com a direita sobre a string, lendo o índice e o caractere em cada etapa. Isso move a janela uma posição por vez.
for right, ch in enumerate(s):Salte o ponteiro da esquerda
Se o caractere tiver sido visto dentro da janela atual, mova a esquerda para logo depois da última posição dele. Isso remove a duplicata em um único movimento.
if ch in last and last[ch] >= left:
left = last[ch] + 1Atualize e meça
Registre a nova posição desse caractere; então, a janela da esquerda até a direita não terá duplicatas. Seu comprimento é right menos left mais um.
last[ch] = right
best = max(best, right - left + 1)Por que a verificação é importante
A verificação last[ch] >= left é essencial. Sem ela, uma posição antiga fora da janela faria a esquerda recuar indevidamente.
Tempo e espaço lineares
Cada caractere é visitado uma vez e a esquerda só avança para a frente, portanto a varredura é O(n). O dicionário usa espaço proporcional aos caracteres distintos.
Cubra os casos extremos
Uma string vazia tem resposta zero, e uma string formada por uma única letra repetida tem resposta um. Verifique ambos os casos antes de enviar para evitar um WA sorrateiro.
O padrão reutilizável
O mapa de caracteres vistos por último junto com um ponteiro esquerdo que salta pode ser generalizado para muitos problemas de unicidade, como janelas com no máximo uma repetição.
Verificação rápida
Você acompanha o último índice de cada caractere enquanto procura a subcadeia única mais longa.
Recapitulação
Deslize uma janela de caracteres únicos, armazene cada última posição e salte a esquerda para depois das repetições. Isso resolve o problema clássico em O(n). ✅
Perguntas Frequentes
A aula “Maior Substring sem Repetições” é grátis?
Sim — o texto completo de “Maior Substring sem Repetições” é grátis para ler aqui na web. Para praticá-la interativamente (um editor de código integrado e um tutor de IA 24/7) e desbloquear o restante do curso de Coding Interview Prep, atualize para CoddyKit PRO. O curso de Coding Interview Prep inclui 4 aulas no total.
O que vou aprender em “Maior Substring sem Repetições”?
Acompanhe as últimas posições vistas em uma janela. Você pratica Coding Interview Prep com código prático que executa diretamente no navegador, e um tutor de IA 24/7 responde suas dúvidas enquanto trabalha na aula.
Preciso ter experiência prévia para começar Coding Interview Prep?
Nenhuma experiência prévia é necessária. Coding Interview Prep no CoddyKit é estruturado para alunos iniciantes até avançados, então você pode começar aqui ou desde o início e aprender no seu ritmo. Esta é a aula 3 de 4.
Quanto tempo leva a aula “Maior Substring sem Repetições”?
A maioria das aulas CoddyKit leva cerca de 5–10 minutos. Cada uma é compacta e interativa, então você faz progresso constante e retoma exatamente de onde parou entre web e app.
Posso escrever e executar código nesta aula de Coding Interview Prep?
Sim. Cada aula de Coding Interview Prep inclui um editor de código integrado, então você escreve e executa código real direto no navegador e recebe feedback de IA instantaneamente — nenhuma configuração local necessária.
Todas as aulas deste curso
- Somas em Janelas de Tamanho Fixo
- Janela Variável com Dois Ponteiros
- Maior Substring sem Repetições
- Conte Janelas que Satisfazem uma Regra