Longest Substring Without Repeating Characters

O Longest Substring Without Repeating Characters é um problema clássico de algoritmos que pede o comprimento da maior substring contínua de uma string que não contém caracteres repetidos.

---

Enunciado (forma comum)

Dada uma string s, encontre o comprimento da maior substring sem repetir caracteres.

Exemplo

• Entrada: "abcabcbb"
• Saída: 3
• Explicação: "abc" é a maior substring sem repetições.

---

Ideia central

Usa-se a técnica de sliding window (janela deslizante) para manter uma janela válida (sem repetições) enquanto percorremos a string uma única vez.

A janela é definida por dois índices:

• left: início da janela
• right: fim da janela (índice atual do loop)

Mantemos também uma estrutura (normalmente um mapa/hash) que guarda a última posição em que cada caractere apareceu.

---

Algoritmo (Sliding Window com Hash Map)

1. Inicialize:

   • left = 0
   • max_len = 0
   • last_seen = {} (caractere → índice)

2. Percorra a string com right:

   • Se s[right] já apareceu dentro da janela atual (last_seen[c] >= left), mova left para last_seen[c] + 1

   • Atualize last_seen[c] = right

   • Atualize o tamanho máximo:

     max_len = max(max_len, right - left + 1)
     

3. Retorne max_len.

---

Exemplo passo a passo ("abba")

right	char	left	ação
0	a	0	janela = “a”
1	b	0	janela = “ab”
2	b	2	repetição → move left
3	a	2	janela = “ba”

Resultado: 2

---

Implementação em Python

def lengthOfLongestSubstring(s: str) -> int:
    last_seen = {}
    left = 0
    max_len = 0
 
    for right, c in enumerate(s):
        if c in last_seen and last_seen[c] >= left:
            left = last_seen[c] + 1
 
        last_seen[c] = right
        max_len = max(max_len, right - left + 1)
 
    return max_len

---

Complexidade

• Tempo: O(n) Cada caractere é processado no máximo duas vezes (entrada e saída da janela).
• Espaço: O(min(n, k)) Onde k é o tamanho do alfabeto (ex.: 128 para ASCII).

---

Observações importantes

• A condição last_seen[c] >= left é essencial para evitar mover a janela para trás.
• Esse padrão de sliding window + hash map aparece em muitos problemas de strings e entrevistas.
• É uma solução ótima e esperada em entrevistas técnicas (ex.: LeetCode #3).