Contagem e Agrupamento por Frequência
Use Counter e defaultdict para contar frequências de caracteres, agrupar anagramas por chave ordenada e encontrar os elementos mais frequentes.
Contagem e Agrupamento por Frequência é uma aula grátis de DSA 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 DSA Interview Prep, e seu progresso é sincronizado entre a web e o app CoddyKit. O curso de DSA Interview Prep inclui 4 aulas no total.
Contagem de frequências: o padrão central
A contagem de frequências está entre os padrões mais versáteis em entrevistas de programação. Ao contabilizar quantas vezes cada elemento aparece em uma lista ou cadeia de caracteres, você pode responder a perguntas sobre duplicatas, anagramas, elementos mais comuns e arranjos válidos em O(n) — muito melhor do que a alternativa de ordenar e percorrer, que tem complexidade O(n log n).
O Counter e o defaultdict(int) do Python são as ferramentas padrão. Ambos criam um mapeamento de elemento para contagem; o Counter também oferece suporte a operações aritméticas e a most_common.
from collections import Counter
words = ['apple', 'banana', 'apple', 'cherry', 'banana', 'apple']
freq = Counter(words)
print(freq) # Counter({'apple':3,'banana':2,'cherry':1})
print(freq['apple']) # 3
print(freq['grape']) # 0 (not KeyError)
print(freq.most_common(2)) # [('apple',3),('banana',2)]Anagrama válido (LeetCode 242)
LeetCode 242, «Anagrama válido»: determine se duas cadeias de caracteres são anagramas uma da outra. Duas cadeias de caracteres são anagramas quando têm as mesmas frequências de caracteres. Compare os objetos Counter ou ordene as duas cadeias. Usar Counter tem complexidade O(n), enquanto ordenar tem complexidade O(n log n). A abordagem com Counter é ideal e expressa diretamente a definição.
from collections import Counter
def isAnagram(s, t):
return Counter(s) == Counter(t)
# Alternative: manual frequency array for lowercase letters only
def isAnagram_arr(s, t):
if len(s) != len(t):
return False
freq = [0] * 26
for c in s: freq[ord(c) - ord('a')] += 1
for c in t: freq[ord(c) - ord('a')] -= 1
return all(f == 0 for f in freq)
print(isAnagram('anagram', 'nagaram')) # True
print(isAnagram('rat', 'car')) # False
print(isAnagram_arr('listen', 'silent')) # TrueAgrupamento de anagramas (LeetCode 49)
LeetCode 49, «Agrupamento de anagramas»: dada uma lista de cadeias de caracteres, agrupe todos os anagramas. A ideia principal é que os anagramas têm a mesma sequência ordenada de caracteres. Use um defaultdict(list) indexado pela tupla ordenada da cadeia de caracteres (tuplas podem ser usadas como chaves de hash). Cada grupo reúne elementos sob a mesma chave. Tempo: O(n × L log L), em que L é o comprimento máximo da cadeia de caracteres.
from collections import defaultdict
def groupAnagrams(strs):
groups = defaultdict(list)
for s in strs:
key = tuple(sorted(s)) # hashable canonical form
groups[key].append(s)
return list(groups.values())
print(groupAnagrams(['eat','tea','tan','ate','nat','bat']))
# [['eat','tea','ate'], ['tan','nat'], ['bat']]
# Alternative key: tuple of 26 character counts (O(L) not O(L log L))
def groupAnagrams_v2(strs):
groups = defaultdict(list)
for s in strs:
key = tuple(ord(c) - ord('a') for c in sorted(s))
groups[tuple(Counter(s)[chr(ord('a')+i)] for i in range(26))].append(s)
return list(groups.values())
K elementos mais frequentes (LeetCode 347)
LeetCode 347, «K elementos mais frequentes»: retorne os k elementos mais frequentes. Uma abordagem direta tem complexidade O(n log n): conte as frequências, ordene pela contagem em ordem decrescente e pegue os primeiros k elementos. A abordagem ideal, com complexidade O(n), usa ordenação por baldes: crie baldes indexados pela frequência (de 1 a n), coloque cada elemento no balde correspondente à sua frequência e, em seguida, percorra os baldes da frequência mais alta para a mais baixa, coletando k elementos.
from collections import Counter
def topKFrequent(nums, k):
freq = Counter(nums)
# Bucket sort by frequency
buckets = [[] for _ in range(len(nums) + 1)]
for num, count in freq.items():
buckets[count].append(num)
result = []
for i in range(len(buckets) - 1, -1, -1):
result.extend(buckets[i])
if len(result) >= k:
return result[:k]
return result
print(topKFrequent([1,1,1,2,2,3], 2)) # [1, 2]
print(topKFrequent([1], 1)) # [1]Ordenar caracteres por frequência (LeetCode 451)
LeetCode 451, «Ordenar caracteres por frequência»: reorganize uma cadeia de caracteres para que os caracteres apareçam em ordem decrescente de frequência. Conte as frequências, ordene os caracteres pela frequência em ordem decrescente e concatene-os. Usar most_common é a abordagem mais clara em Python. Tempo: O(n log n) para ordenar os caracteres distintos pela frequência.
from collections import Counter
def frequencySort(s):
freq = Counter(s)
return ''.join(ch * count for ch, count in freq.most_common())
print(frequencySort('tree')) # 'eetr' or 'eert'
print(frequencySort('cccaaa')) # 'cccaaa' or 'aaaccc'
print(frequencySort('Aabb')) # 'bbAa' or 'bbaA'Agendador de tarefas (LeetCode 621)
LeetCode 621, «Agendador de tarefas»: dadas tarefas e um período de espera n, encontre o tempo mínimo para concluir todas as tarefas. A ideia fundamental é que a tarefa mais frequente determina a estrutura. Organize cópias da tarefa mais frequente com n intervalos entre elas. O tempo mínimo total = máximo((contagem máxima - 1) * (n + 1) + número de tarefas com contagem máxima, número total de tarefas). Se houver tarefas diferentes suficientes para preencher os intervalos, o tempo ocioso será 0.
from collections import Counter
def leastInterval(tasks, n):
freq = Counter(tasks)
max_count = max(freq.values())
# How many tasks share the max frequency
num_max = sum(1 for v in freq.values() if v == max_count)
# Minimum slots needed based on most frequent task
min_slots = (max_count - 1) * (n + 1) + num_max
return max(min_slots, len(tasks))
print(leastInterval(['A','A','A','B','B','B'], 2)) # 8
print(leastInterval(['A','A','A','B','B','B'], 0)) # 6
print(leastInterval(['A','A','A','A','B','B','B','C','C','D'], 2)) # 10Votação da maioria com Counter
LeetCode 169, «Elemento majoritário»: encontre o elemento que aparece mais de n/2 vezes. Embora a votação de Boyer-Moore seja a solução ideal em espaço O(1), usar Counter.most_common(1) resolve o problema diretamente em O(n) de tempo e O(n) de espaço. Em entrevistas que mencionem espaço O(1), apresente Boyer-Moore como complemento; em entrevistas que permitam espaço adicional, Counter é mais simples.
from collections import Counter
def majorityElement_counter(nums):
freq = Counter(nums)
return freq.most_common(1)[0][0]
# Boyer-Moore O(1) space
def majorityElement_moore(nums):
candidate, count = None, 0
for num in nums:
if count == 0:
candidate = num
count += (1 if num == candidate else -1)
return candidate
nums = [2, 2, 1, 1, 2, 2, 2]
print(majorityElement_counter(nums)) # 2
print(majorityElement_moore(nums)) # 2Primeiro caractere não repetido
LeetCode 387, «Primeiro caractere único em uma cadeia»: encontre o índice do primeiro caractere que aparece exatamente uma vez. Abordagem em duas passagens: a primeira cria uma contagem de frequências; a segunda encontra o primeiro caractere cuja contagem é 1. Tempo: O(n), espaço: O(1), pois o alfabeto é fixo e tem 26 caracteres.
from collections import Counter
def firstUniqChar(s):
freq = Counter(s)
for i, ch in enumerate(s):
if freq[ch] == 1:
return i
return -1
print(firstUniqChar('leetcode')) # 0 (l)
print(firstUniqChar('loveleetcode')) # 2 (v)
print(firstUniqChar('aabb')) # -1Soma do subvetor igual a K (LeetCode 560)
LeetCode 560, «Soma do subvetor igual a K»: conte os subvectores cuja soma seja k. A força bruta tem complexidade O(n²). A abordagem O(n) mantém uma soma de prefixo acumulada e um mapa de frequências das somas de prefixo vistas até então. Para cada posição i, a quantidade de subvectores terminados em i com soma k é igual à quantidade de somas de prefixo anteriores iguais à soma de prefixo atual menos k. Inicialize o mapa com {0: 1} para lidar com subvectores que começam no índice 0.
from collections import defaultdict
def subarraySum(nums, k):
freq = defaultdict(int)
freq[0] = 1 # prefix sum of 0 seen once (empty prefix)
prefix_sum = 0
count = 0
for num in nums:
prefix_sum += num
# How many earlier prefix sums allow a k-sum subarray ending here
count += freq[prefix_sum - k]
freq[prefix_sum] += 1
return count
print(subarraySum([1, 1, 1], 2)) # 2
print(subarraySum([1, 2, 3], 3)) # 2
print(subarraySum([1, -1, 1, -1, 1], 0)) # 4Aritmética e interseção de Counter
O Counter oferece suporte a operações aritméticas: + mescla as contagens (somando-as), - subtrai as contagens (limitando o resultado a 0), & obtém o mínimo (interseção) e | obtém o máximo (união). Essas operações simplificam problemas como «encontrar caracteres comuns em várias cadeias» ou «remover o número mínimo de caracteres para tornar uma cadeia um anagrama de outra».
from collections import Counter
A = Counter('abccdd')
B = Counter('ccdde')
print('Add: ', dict(A + B)) # sum of counts
print('Subtract: ', dict(A - B)) # A - B, clipped at 0
print('Intersect:', dict(A & B)) # min of shared counts
print('Union: ', dict(A | B)) # max counts
# Min steps to make s anagram of t (LeetCode 1347)
s, t = 'leetcode', 'practice'
diff = Counter(t) - Counter(s)
print('Chars to add:', sum(diff.values())) # 5Resumo: quando usar a contagem de frequências
Recorra à contagem de frequências quando o problema envolver: verificar se duas cadeias são equivalentes, exceto pela reordenação (anagrama); encontrar os elementos mais ou menos comuns; validar se uma coleção contém os «ingredientes» corretos; ou transformar um problema de subvetor ou subcadeia em um problema de soma de prefixo com mapa. O essencial é que a ordem dentro de um grupo não importa — apenas as contagens importam.
Use sempre Counter para manter a clareza; mude para um dict simples ou um vetor somente quando precisar de um controle mais preciso ou de espaço O(1) estrito com um alfabeto limitado.
Verificação rápida
Teste sua compreensão dos conceitos de Estruturas de Dados e Algoritmos — Preparação para Entrevistas de Programação abordados nesta lição.
Recapitulação da lição
Nesta lição, você aprendeu: Counter fornece contagem de frequências em O(n) com most_common, operadores aritméticos e acesso com valor padrão zero, o agrupamento por forma canônica (tupla ordenada) resolve o agrupamento de anagramas em O(nL log L) e a soma de prefixo com mapa de frequências transforma a soma de subvetor igual a k de O(n²) em O(n). Em seguida, abordaremos o problema da sequência consecutiva mais longa e o projeto de cache LRU.
Perguntas Frequentes
A aula “Contagem e Agrupamento por Frequência” é grátis?
Sim — o texto completo de “Contagem e Agrupamento por Frequência” é 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 DSA Interview Prep, atualize para CoddyKit PRO. O curso de DSA Interview Prep inclui 4 aulas no total.
O que vou aprender em “Contagem e Agrupamento por Frequência”?
Use Counter e defaultdict para contar frequências de caracteres, agrupar anagramas por chave ordenada e encontrar os elementos mais frequentes. Você pratica DSA 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 DSA Interview Prep?
Nenhuma experiência prévia é necessária. DSA 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 “Contagem e Agrupamento por Frequência”?
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 DSA Interview Prep?
Sim. Cada aula de DSA 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
- Internals de Funções Hash e Tratamento de Colisões
- Two-Sum e Suas Muitas Variantes
- Contagem e Agrupamento por Frequência
- Maior Sequência Consecutiva e Cache LRU