Algoritmo 12 — Sliding Window — Longest Substring Without Repeating Characters

Sumário

• Apresentação do Problema
• Solução
• Execução do Algoritmo
• Conclusão

Apresentação do Problema

O problema pode ser encontrado aqui: Longest Substring Without Repeating Characters — LeetCode

Esse problema trata de: dada uma string s, temos de encontrar o comprimento da mais longa substring sem repetir caracteres. Por exemplo, imagine que tenhamos a seguinte string: s = “abcabc”, a substring mais longa sem repetir qualquer caractere é “abc” e com o tamanho de 3, logo devemos retornar 3, pois queremos o seu comprimento.

Solução do Problema

Abaixo vemos uma solução do problema:

func lengthOfLongestSubstring(s string) int {
 mapa := make(map[byte]bool)
 l := 0
 res := 0

 for r := range s {
  for mapa[s[r]] {
   delete(mapa, s[l])
   l++
  }
  mapa[s[r]] = true
  res = max(res, r-l+1)
 }
 return res
}

func max(a, b int) int {
 if a > b {
  return a
 }
 return b
}

Dentro da função, um mapa chamado “mapa” é criado para armazenar os caracteres e um booleano indicando se o caracter já foi visto. Duas variáveis inteiras, “l” e “res”, são inicializadas com valor 0. O “l” será usada para marcar o início da janela de verificação atual, e “res” para armazenar o comprimento da maior substring encontrada. O loop principal (for r := range s) itera sobre cada caractere da string “s”, usando “r” como índice. Dentro do loop, há outro loop que verifica se o caracter atual (s[r]) já está no mapa. Se estiver, ele remove o caractere no início da janela (s[l]) do mapa e move “l” para frente. Após sair do loop interno, o caractere atual é adicionado ao mapa e “res” é atualizado se o comprimento da substring atual (dado por “r-l+1”) for maior que o valor atual de “res”. Ao final, a função retorna “res”, que é o comprimento da maior substring sem repetição de caracteres encontrada. Caso não tenha entendido, aqui vai uma execução passo a passo para a string: “abcabcbb”, perceba o funcionamento principalmente da parte “r-l+1” e a beleza do for mais interno.

Execução do Algoritmo

Na primeira iteração com o caractere ‘a’, o mapa, que rastreia os caracteres já vistos, não contém ‘a’, então este é adicionado ao mapa. O resultado res é atualizado para ser o máximo entre ele mesmo e a diferença de índices, que neste caso é 1 (0 - 0 + 1). Agora, o mapa contém {'a': true} e res é 1.

Na segunda iteração, com o caractere ‘b’, o mapa ainda não contém ‘b’, então ‘b’ é adicionado. O resultado res é atualizado para 2, pois a diferença de índices agora é 2 - 0 + 1. O mapa agora é {'a': true, 'b': true}.

No terceiro passo, com o caractere ‘c’, o processo se repete. ‘c’ é adicionado ao mapa e res torna-se 3 (3 - 0 + 1), com o mapa sendo {'a': true, 'b': true, 'c': true}.

Agora o laço interno vai possuir utilidade: Quando o quarto caractere, outro ‘a’, é encontrado, o algoritmo detecta que ‘a’ já está no mapa. Ele então remove caracteres do início da janela até que ‘a’ possa ser adicionado sem duplicidade. ‘a’ é removido, l é incrementado para 1, e 'a' é adicionado novamente ao mapa. res é atualizado, mas permanece 3 (3 - 1 + 1), e o mapa agora é {'b': true, 'c': true, 'a': true}.

O processo se repete para os próximos caracteres. Quando ‘b’ e depois ‘c’ são encontrados novamente, eles são tratados da mesma maneira, removendo o caractere antigo e adicionando o novo. No entanto, res não aumenta porque as novas substrings encontradas são menores ou iguais a 3 caracteres.

Finalmente, após percorrer toda a string, o algoritmo conclui que o comprimento da maior substring sem repetição é 3, correspondendo à substring “abc”.

Conclusão

O algoritmo eficientemente identifica a maior substring sem repetição de caracteres em uma string dada.

Quanto a complexidade de tempo, o algoritmo itera sobre cada caractere da string uma vez com o índice “r”(direita da janela deslizante). Dentro de cada iteração, pode haver uma iteração interna para ajustar o índice “l” (esquerda da janela deslizante) quando um caractere repetido é encontrado. No pior caso, cada caractere pode ser visitado duas vezes: uma pelo índice “r” e outra pelo ajuste de “l”. Assim, no pior caso, a complexidade de tempo é O(2n), que é simplificada para O(n), onde n é o comprimento da string. Portanto, a complexidade de tempo é linear em relação ao tamanho da string.

A complexidade de espaço é um pouco difícil de definir devido ao mapa depender do conjunto de caracteres da string. No pior caso podemos ter O(n) onde n é o comprimento da string.

Redigido por Gabriel Palitot, revisado por Eliabe Bastos.