Valid Anagram e Contains Duplicate — HashMap e HashSet na Prática

Dois problemas muito conhecidos do LeetCode são:

• Valid Anagram
• Contains Duplicate

Apesar de parecerem problemas diferentes, ambos ensinam um conceito extremamente importante:

Como usar estruturas de dados para verificar rapidamente a existência e a frequência de elementos.

Eles são ótimos exercícios para aprender:

• HashMap
• HashSet
• Contagem de frequência
• Comparação de strings
• Detecção de duplicatas
• Complexidade O(n)

Neste artigo, vamos entender os dois problemas e as principais estratégias para resolvê-los.

1. Valid Anagram

O problema Valid Anagram pede para verificar se duas strings são anagramas.

Um anagrama acontece quando podemos reorganizar as letras de uma palavra para formar outra, utilizando exatamente as mesmas letras e a mesma quantidade de cada uma.

Por exemplo:

anagram
nagaram

Podemos reorganizar:

anagram
   ↓
nagaram

As letras são as mesmas:

a → 3
n → 2
g → 1
r → 1
m → 1

Portanto:

anagram

e:

nagaram

são anagramas.

2. Exemplos

Exemplo válido

s = "listen"

t = "silent"

As letras são:

listen
silent

Mesma quantidade de:

l
i
s
t
e
n

Resultado:

true

Exemplo inválido

s = "rat"

t = "car"

Temos:

rat

car

As letras são diferentes.

Resultado:

false

3. A ideia principal

Para descobrir se duas palavras são anagramas, precisamos comparar a frequência das letras.

Por exemplo:

s = "aabbc"

t = "ababc"

Contagem de s:

a → 2
b → 2
c → 1

Contagem de t:

a → 2
b → 2
c → 1

As contagens são iguais.

Logo:

true

4. Usando um HashMap

Podemos utilizar um Map para armazenar a quantidade de vezes que cada letra aparece.

Em TypeScript:

function isAnagram(s: string, t: string): boolean {
  if (s.length !== t.length) {
    return false;
  }

  const count = new Map<string, number>();

  for (const char of s) {
    count.set(char, (count.get(char) ?? 0) + 1);
  }

  for (const char of t) {
    const current = count.get(char);

    if (!current) {
      return false;
    }

    count.set(char, current - 1);
  }

  return true;
}

5. Entendendo a solução

Imagine:

s = "anagram"

t = "nagaram"

Primeiro contamos as letras de s:

Map

a → 3
n → 2
g → 1
r → 1
m → 1

Depois percorremos t.

Encontramos:

n

Diminuímos:

n → 2

Encontramos:

a

Diminuímos:

a → 2

Continuamos até chegar a:

a → 0
n → 0
g → 0
r → 0
m → 0

Todas as letras foram encontradas na quantidade correta.

Resultado:

true

6. Uma solução ainda mais simples

Também podemos contar as duas strings separadamente.

function isAnagram(s: string, t: string): boolean {
  if (s.length !== t.length) {
    return false;
  }

  const countS = new Map<string, number>();
  const countT = new Map<string, number>();

  for (const char of s) {
    countS.set(char, (countS.get(char) ?? 0) + 1);
  }

  for (const char of t) {
    countT.set(char, (countT.get(char) ?? 0) + 1);
  }

  return areMapsEqual(countS, countT);
}

Porém, precisamos comparar os dois Maps.

Por isso, a primeira solução costuma ser mais elegante.

7. Solução utilizando ordenação

Outra possibilidade é ordenar as duas strings.

Por exemplo:

listen

Ordenando:

eilnst

E:

silent

Ordenando:

eilnst

Se forem iguais:

true

Em TypeScript:

function isAnagram(s: string, t: string): boolean {
  return (
    s.split("").sort().join("") ===
    t.split("").sort().join("")
  );
}

Essa solução é muito simples de escrever.

Porém, a ordenação possui complexidade:

O(n log n)

Enquanto a solução com Map possui:

O(n)

Por isso, em entrevistas técnicas, a solução com contagem geralmente é mais interessante.

8. Complexidade do Valid Anagram

Utilizando Map:

Time Complexity: O(n)

Space Complexity: O(n)

Precisamos percorrer as strings.

O Map armazena as frequências das letras.

Se o conjunto de caracteres for limitado, por exemplo apenas letras minúsculas de a até z, podemos utilizar um array de tamanho fixo e reduzir o espaço utilizado.

9. Contains Duplicate

Agora temos outro problema:

Dado um array de números, descubra se existe algum valor duplicado.

Por exemplo:

[1, 2, 3, 1]

Temos:

1

aparecendo duas vezes.

Resultado:

true

Outro exemplo:

[1, 2, 3, 4]

Nenhum número aparece mais de uma vez.

Resultado:

false

10. A solução mais simples

Uma possibilidade é comparar cada número com todos os outros.

function containsDuplicate(numbers: number[]): boolean {
  for (let i = 0; i < numbers.length; i++) {
    for (let j = i + 1; j < numbers.length; j++) {
      if (numbers[i] === numbers[j]) {
        return true;
      }
    }
  }

  return false;
}

Essa solução funciona.

Porém:

Time Complexity: O(n²)

Se o array for muito grande, pode ficar lento.

11. Usando um HashSet

A melhor solução é utilizar um Set.

Um Set armazena valores únicos.

Por exemplo:

const numbers = new Set<number>();

numbers.add(1);
numbers.add(2);
numbers.add(3);

Temos:

Set

1
2
3

Se tentarmos adicionar 1 novamente:

numbers.add(1);

O Set continuará contendo apenas:

1
2
3

Não haverá um segundo 1.

12. Solução do Contains Duplicate

function containsDuplicate(numbers: number[]): boolean {
  const seen = new Set<number>();

  for (const number of numbers) {
    if (seen.has(number)) {
      return true;
    }

    seen.add(number);
  }

  return false;
}

A lógica é simples:

Para cada número:

    Se já existe no Set:
        Encontramos uma duplicata

    Caso contrário:
        Adicionamos ao Set

13. Exemplo passo a passo

Temos:

numbers = [1, 2, 3, 1]

Começamos:

Set = {}

Primeiro:

1

Não existe.

Adicionamos:

Set = {1}

Segundo:

2

Não existe.

Set = {1, 2}

Terceiro:

3

Não existe.

Set = {1, 2, 3}

Quarto:

1

Já existe:

Set = {1, 2, 3}
         ↑
      encontrado

Retornamos:

true

14. Uma solução ainda mais curta

Em JavaScript e TypeScript, existe uma solução extremamente simples:

function containsDuplicate(numbers: number[]): boolean {
  return new Set(numbers).size !== numbers.length;
}

A lógica é:

Array original:

[1, 2, 3, 1]

Length:

4

Depois:

Set:

{1, 2, 3}

Size:

3

Como:

3 !== 4

Sabemos que existia uma duplicata.

15. Complexidade do Contains Duplicate

Utilizando Set:

Time Complexity: O(n)

Space Complexity: O(n)

Percorremos o array uma vez.

O Set armazena os valores encontrados.

16. O que Valid Anagram e Contains Duplicate têm em comum?

Os dois problemas utilizam a mesma ideia fundamental:

Armazenar informações já encontradas para evitar trabalho desnecessário.

No Valid Anagram:

Map

caractere → quantidade

Por exemplo:

a → 3
b → 2
c → 1

No Contains Duplicate:

Set

valor

Por exemplo:

1
2
3

A diferença é:

Map

é utilizado quando precisamos armazenar uma relação:

chave → valor

Enquanto:

Set

é utilizado quando precisamos apenas saber:

"Esse elemento já existe?"

17. HashMap vs HashSet

Podemos pensar assim:

HashMap

Use quando você precisa guardar informações sobre algo.

Map

"user123" → "Peterson"

Ou:

"a" → 3

Ou:

"produto123" → 59.90

HashSet

Use quando você só precisa saber se algo existe.

Set

"user123"
"user456"
"user789"

Pergunta:

"user123" existe?

Resposta:

true

18. Exemplo prático: validar usuários duplicados

Imagine que sua aplicação recebe uma lista de usernames:

const usernames = [
  "peterson",
  "joao",
  "maria",
  "peterson"
];

Precisamos garantir que não existam usuários duplicados.

Podemos usar:

function hasDuplicateUsernames(
  usernames: string[]
): boolean {
  const seen = new Set<string>();

  for (const username of usernames) {
    if (seen.has(username)) {
      return true;
    }

    seen.add(username);
  }

  return false;
}

Resultado:

true

O usuário:

peterson

aparece duas vezes.

Esse mesmo padrão pode ser utilizado para validar:

• Emails
• IDs
• CPF
• Códigos de produtos
• IDs de pedidos
• Números de documentos

19. Exemplo prático: frequência de palavras

Agora imagine um sistema que analisa um texto.

"hello world hello"

Queremos descobrir quantas vezes cada palavra aparece.

Podemos utilizar um Map:

function countWords(text: string): Map<string, number> {
  const count = new Map<string, number>();

  const words = text.split(" ");

  for (const word of words) {
    count.set(
      word,
      (count.get(word) ?? 0) + 1
    );
  }

  return count;
}

Resultado:

hello → 2
world → 1

Esse é exatamente o mesmo conceito utilizado no:

Valid Anagram

Apenas estamos contando palavras em vez de letras.

20. Quando utilizar cada estrutura?

Uma regra prática:

Preciso saber se algo já apareceu?

↓

Set

Por exemplo:

"Já encontrei esse ID?"

Use:

Set

Agora:

Preciso saber quantas vezes apareceu?

↓

Map

Por exemplo:

"Quantas vezes essa letra apareceu?"

Use:

Map

Ou:

Preciso associar uma informação a outra?

↓

Map

Por exemplo:

userId → user

21. Comparação

ProblemaEstruturaObjetivoComplexidadeValid AnagramMapContar frequênciaO(n)Contains DuplicateSetDetectar duplicatasO(n)

Podemos resumir:

Valid Anagram

String
   │
   ▼
Contagem de frequência
   │
   ▼
Map

E:

Contains Duplicate

Array
   │
   ▼
Elementos já vistos
   │
   ▼
Set

Conclusão

Os problemas Valid Anagram e Contains Duplicate parecem simples, mas ensinam conceitos extremamente importantes.

No Valid Anagram, precisamos descobrir se duas strings possuem exatamente os mesmos caracteres na mesma quantidade.

A solução eficiente utiliza um Map para controlar a frequência:

const count = new Map<string, number>();

Já no Contains Duplicate, precisamos apenas descobrir se algum elemento apareceu anteriormente.

A solução ideal utiliza um Set:

const seen = new Set<number>();

A principal diferença pode ser resumida assim:

Map

"Quero armazenar informações sobre um elemento."

Set

"Quero saber se esse elemento já existe."

Ambas as estruturas permitem buscar informações de maneira muito eficiente e, na maioria dos casos, possibilitam soluções com:

O(n)

em vez de:

O(n²)

A grande lição desses problemas é aprender a reconhecer quando uma estrutura de dados pode eliminar a necessidade de comparar cada elemento com todos os outros.

Quando precisar lembrar o que já encontrou, pense em Set ou Map.