0Pricing
Coding Interview Prep · Aula

Anagramas e Mapas de Frequência de Caracteres

Resolva group-anagrams, valid-anagram e permutation-in-string usando arrays de frequências e mapas hash para obter soluções em O(n).

Anagramas e Mapas de Frequência de Caracteres é 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.

O que é um anagrama

Duas strings são anagramas quando contêm os mesmos caracteres com as mesmas frequências, apenas em uma ordem diferente. “amor” e “roma” são anagramas. A verificação mais simples é ordenar as duas strings e compará-las: O(n log n). Para obter soluções O(n), compare mapas de frequências de caracteres. Problemas de anagramas são comuns em entrevistas sobre strings porque testam várias técnicas: tabelas de dispersão, ordenação e vetores de frequências.

def is_anagram_sort(s, t):
    return sorted(s) == sorted(t)  # O(n log n)

def is_anagram_counter(s, t):
    from collections import Counter
    return Counter(s) == Counter(t)  # O(n)

def is_anagram_array(s, t):
    if len(s) != len(t): return False
    freq = [0] * 26
    for a, b in zip(s, t):
        freq[ord(a) - ord('a')] += 1
        freq[ord(b) - ord('a')] -= 1
    return all(f == 0 for f in freq)  # O(n)

print(is_anagram_array('anagram', 'nagaram'))  # True
print(is_anagram_array('rat', 'car'))           # False

Vetor de frequências para letras minúsculas

Quando o conjunto de caracteres é limitado, por exemplo, apenas letras minúsculas de a a z, substitua uma tabela de dispersão por um vetor de frequências de tamanho 26. O indexador ord(c) - ord('a') mapeia 'a'→0, 'b'→1, ..., 'z'→25. Na prática, os vetores são mais rápidos do que os dicionários devido à localidade de cache e à ausência do custo da dispersão. Esse truque aparece nos problemas de anagrama válido, permutação em string e permutação de palíndromo.

def build_freq(s):
    freq = [0] * 26
    for c in s:
        freq[ord(c) - ord('a')] += 1
    return freq

def is_anagram_fast(s, t):
    return len(s) == len(t) and build_freq(s) == build_freq(t)

# Palindrome permutation: at most one odd-count character
def can_form_palindrome(s):
    freq = build_freq(s)
    odd_count = sum(1 for f in freq if f % 2 == 1)
    return odd_count <= 1

print(can_form_palindrome('carerace'))  # True ('racecar')
print(can_form_palindrome('hello'))     # False

Agrupamento de anagramas

Agrupe uma lista de strings para que todos os anagramas apareçam juntos. A solução canônica O(n×m log m) usa a string ordenada como chave de uma tabela de dispersão. Todos os anagramas produzem a mesma chave ordenada e, por isso, vão para o mesmo grupo. Uma variante O(n×m) usa uma tupla de contagens de caracteres como chave — é mais lenta para calcular, mas evita completamente a ordenação. A abordagem com chave ordenada quase sempre é preferida por ser mais clara.

from collections import defaultdict

def group_anagrams(strs):
    groups = defaultdict(list)
    for s in strs:
        key = tuple(sorted(s))  # or ''.join(sorted(s))
        groups[key].append(s)
    return list(groups.values())

words = ['eat','tea','tan','ate','nat','bat']
result = group_anagrams(words)
for g in sorted(result, key=len, reverse=True):
    print(sorted(g))
# ['ate', 'eat', 'tea']
# ['nat', 'tan']
# ['bat']

Chave de anagrama com tupla de contagens

Na variante O(n×m) de agrupamento de anagramas, represente a frequência de cada string como uma tupla com 26 contagens: tuple(freq_array). Isso evita a ordenação, mas exige O(26×n×m) operações para construir todas as chaves. Tuplas podem ser usadas em tabelas de dispersão no Python, o que as torna chaves válidas de dicionários. Vale mencionar essa variante quando o entrevistador pedir “qualquer solução O(n×m)”, pois ela demonstra que você entende diferentes compromissos.

from collections import defaultdict

def group_anagrams_count(strs):
    groups = defaultdict(list)
    for s in strs:
        freq = [0] * 26
        for c in s:
            freq[ord(c) - ord('a')] += 1
        key = tuple(freq)  # tuple is hashable
        groups[key].append(s)
    return list(groups.values())

print(group_anagrams_count(['eat','tea','tan','ate','nat','bat']))

K elementos mais frequentes

Encontre os k elementos mais frequentes de um vetor. Contador + fila de prioridade: construa um mapa de frequências em O(n) e depois extraia as k maiores frequências usando uma fila de prioridade mínima de tamanho k ou Counter.most_common(k). Uma abordagem O(n) de ordenação por baldes cria baldes indexados pela frequência, de 0 a n, e coleta os elementos na ordem inversa de frequência — uma solução elegante quando k é grande.

from collections import Counter
import heapq

def top_k_frequent_heap(nums, k):
    freq = Counter(nums)
    return heapq.nlargest(k, freq, key=freq.get)

def top_k_frequent_bucket(nums, k):
    freq = Counter(nums)
    buckets = [[] for _ in range(len(nums) + 1)]
    for num, cnt in freq.items():
        buckets[cnt].append(num)
    result = []
    for i in range(len(buckets)-1, -1, -1):
        result.extend(buckets[i])
        if len(result) >= k: break
    return result[:k]

print(top_k_frequent_heap([1,1,1,2,2,3], 2))   # [1, 2]
print(top_k_frequent_bucket([1,1,1,2,2,3], 2)) # [1, 2]

Mapa de frequências para permutação em string

Determine se alguma permutação da string p aparece como subcadeia de s. O mapa de frequências de uma janela de comprimento |p| deve ser igual ao mapa de frequências de p. Conforme a janela desliza, incremente a contagem do caractere que entra e decremente a contagem do caractere que sai. Comparar dois objetos de contador custa O(26) a cada vez, resultando em O(n×26) = O(n) no total. Acompanhe um contador de caracteres satisfeitos para verificar a igualdade em O(1).

def check_inclusion_fast(p, s):
    if len(p) > len(s): return False
    need = [0] * 26
    have = [0] * 26
    for c in p:
        need[ord(c)-ord('a')] += 1
    for i in range(len(p)):
        have[ord(s[i])-ord('a')] += 1
    if need == have: return True
    for i in range(len(p), len(s)):
        have[ord(s[i])-ord('a')]         += 1
        have[ord(s[i-len(p)])-ord('a')] -= 1
        if need == have: return True
    return False

print(check_inclusion_fast('ab', 'eidbaooo'))  # True
print(check_inclusion_fast('ab', 'eidboaoo'))  # False

Mínimo de caracteres para formar um anagrama

Dadas duas strings, encontre o número mínimo de exclusões de caracteres necessário para transformar uma em um anagrama da outra. Calcule os mapas de frequências das duas strings; a resposta é a soma das diferenças absolutas entre as frequências. Todos os caracteres presentes em uma string, mas ausentes na outra, precisam ser excluídos. Esta solução O(n) usa o padrão de mesclagem e diferença aplicado a mapas de frequências.

from collections import Counter

def min_steps_to_anagram(s, t):
    freq_s = Counter(s)
    freq_t = Counter(t)
    steps = 0
    # For each unique char across both strings:
    all_chars = set(freq_s) | set(freq_t)
    for c in all_chars:
        steps += abs(freq_s.get(c, 0) - freq_t.get(c, 0))
    return steps

# Or more concisely:
def min_steps_counter(s, t):
    diff = Counter(s) - Counter(t)
    return sum(diff.values())

print(min_steps_to_anagram('leetcode', 'practice'))  # 5
print(min_steps_counter('leetcode', 'practice'))      # 5

Mapa de frequências para nota de resgate

Verifique se todos os caracteres de note podem ser fornecidos pelos caracteres de magazine, considerando que cada caractere da revista só pode ser usado uma vez. Construa um mapa de frequências dos caracteres da revista; depois, para cada caractere da nota, diminua a contagem. Se alguma contagem ficar negativa, retorne falso. O tempo é O(n + m) e o espaço é O(1) para entradas restritas a letras minúsculas, usando um vetor com 26 elementos em vez de um dicionário.

def can_construct(note, magazine):
    freq = [0] * 26
    for c in magazine:
        freq[ord(c) - ord('a')] += 1
    for c in note:
        freq[ord(c) - ord('a')] -= 1
        if freq[ord(c) - ord('a')] < 0:
            return False  # insufficient supply
    return True

print(can_construct('aa', 'aab'))    # True
print(can_construct('aa', 'ab'))     # False
print(can_construct('bg', 'efjbdfbdgbjjbghiklgdch'))  # True

Dispersão de subcadeias anagramas mais longas

Para verificar se duas subcadeias da mesma string são anagramas, use uma função de dispersão polinomial das frequências de caracteres que seja comutativa, ou seja, independente da ordem. O XOR dos valores dos caracteres é comutativo e pode ser atualizado em O(1), mas tem alta probabilidade de colisão. Uma abordagem melhor usa dispersão por produto de primos, em que cada caractere é associado a um primo distinto e o produto é independente da ordem. Esta é uma técnica específica para entrevistas avançadas.

# Prime product hash: each char maps to a prime
PRIMES = [2,3,5,7,11,13,17,19,23,29,31,37,41,
          43,47,53,59,61,67,71,73,79,83,89,97,101]

def char_hash(s):
    h = 1
    for c in s:
        h *= PRIMES[ord(c) - ord('a')]
    return h

# Two windows with equal hash are likely anagrams
print(char_hash('listen'))  # same as:
print(char_hash('silent'))  # should match

Lista de verificação de padrões de mapas de frequências

Reconheça estes padrões de entrevistas envolvendo mapas de frequências:

  • Anagrama válido: mesmo comprimento + mesma frequência → igualdade de contadores ou comparação de vetores
  • Agrupamento de anagramas: string ordenada ou tupla de frequências como chave de dicionário
  • k elementos mais frequentes: contador + fila de prioridade ou ordenação por baldes
  • Permutação em string: janela deslizante + comparação de frequências
  • Nota de resgate: mapa de frequências do fornecimento, com redução para a demanda
  • Permutação de palíndromo: no máximo um caractere com contagem ímpar
Tudo se reduz à mesma ideia central: a frequência como uma impressão digital.

from collections import Counter

# Palindrome permutation
def palindrome_permutation(s):
    return sum(v % 2 for v in Counter(s).values()) <= 1

# First unique character
def first_unique(s):
    freq = Counter(s)
    for i, c in enumerate(s):
        if freq[c] == 1:
            return i
    return -1

# Character replacement for longest repeat
def char_replacement(s, k):
    freq = Counter()
    left = best = max_freq = 0
    for right, c in enumerate(s):
        freq[c] += 1
        max_freq = max(max_freq, freq[c])
        if (right - left + 1) - max_freq > k:
            freq[s[left]] -= 1
            left += 1
        best = max(best, right - left + 1)
    return best

print(palindrome_permutation('carerace'))  # True
print(first_unique('leetcode'))             # 0
print(char_replacement('AABABBA', 1))      # 4

O elemento diferente: XOR para frequências

XOR é uma ferramenta poderosa para problemas de frequências quando exatamente um elemento aparece uma quantidade ímpar de vezes. O XOR de um número com ele mesmo se anula para 0: a XOR a = 0. Aplicar XOR a todos os elementos, quando cada valor aparece uma quantidade par de vezes, exceto um, deixa apenas o elemento ímpar. Isso resulta em tempo O(n) e espaço O(1), sem necessidade de uma tabela de dispersão. A técnica pode ser generalizada para encontrar dois números que aparecem uma quantidade ímpar de vezes usando as propriedades de XOR.

def single_number(nums):
    result = 0
    for n in nums:
        result ^= n  # XOR cancels pairs
    return result

print(single_number([4,1,2,1,2]))   # 4
print(single_number([2,2,1]))       # 1

# Find the unique character in an anagram check:
def find_difference(s, t):
    result = 0
    for c in s + t:
        result ^= ord(c)
    return chr(result)

print(find_difference('abcd', 'abcde'))  # 'e'

Verificação rápida

Verifique sua compreensão dos conceitos de Estruturas de Dados & Algoritmos — Preparação para Entrevistas de Programação apresentados nesta lição.

Recapitulação da lição

Nesta lição, você aprendeu que: os mapas de frequências de caracteres são a principal ferramenta para detectar anagramas — use um vetor de 26 elementos para alfabetos limitados ou um contador para caracteres arbitrários; chaves de dicionário baseadas em strings ordenadas ou tuplas de frequências agrupam todos os anagramas em tempo O(n × m log m) ou O(n × m), respectivamente; e XOR elimina pares de forma eficiente em problemas com um único elemento de contagem ímpar, oferecendo tempo O(n) e espaço O(1) quando não é necessário um dicionário. Em seguida, exploraremos técnicas de codificação, reversão e palíndromos em strings.

Perguntas Frequentes

A aula “Anagramas e Mapas de Frequência de Caracteres” é grátis?

Sim — o texto completo de “Anagramas e Mapas de Frequência de Caracteres” é 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 “Anagramas e Mapas de Frequência de Caracteres”?

Resolva group-anagrams, valid-anagram e permutation-in-string usando arrays de frequências e mapas hash para obter soluções em O(n). 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 “Anagramas e Mapas de Frequência de Caracteres”?

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

  1. API de Strings do Python para Entrevistas
  2. Janela Deslizante para Substrings
  3. Anagramas e Mapas de Frequência de Caracteres
  4. Codificação, Reversão e Palíndromos de Strings
← Voltar para Coding Interview Prep