Conteo y agrupación por frecuencia
Use Counter y defaultdict para contar frecuencias de caracteres, agrupe anagramas por clave ordenada y encuentre los elementos más frecuentes mediante top-k.
Conteo y agrupación por frecuencia es una lección gratuita de Coding Interview Prep en CoddyKit. Esta es la lección 3 de 4. Puedes leer la lección completa abajo gratuitamente — luego la practicas en el navegador con un editor de código integrado y un tutor de IA 24/7. Forma parte de la ruta de aprendizaje de Coding Interview Prep, y tu progreso se sincroniza en la web y la app de CoddyKit. El curso de Coding Interview Prep incluye 4 lecciones en total.
Conteo de frecuencias: el patrón fundamental
El conteo de frecuencias es uno de los patrones más versátiles en las entrevistas de programación. Al contabilizar cuántas veces aparece cada elemento en una lista o cadena, puede responder preguntas sobre duplicados, anagramas, elementos más frecuentes y disposiciones válidas en tiempo O(n), mucho mejor que la alternativa de ordenar y recorrer, que cuesta O(n log n).
Counter y defaultdict(int) de Python son las herramientas estándar. Ambas crean una correspondencia entre cada elemento y su cantidad; Counter también admite operaciones aritméticas y 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)]Valid Anagram (LeetCode 242)
LeetCode 242 'Valid Anagram': determine si dos cadenas son anagramas entre sí. Dos cadenas son anagramas si tienen las mismas frecuencias de caracteres. Compare sus objetos Counter o ordene ambas cadenas. Usar Counter cuesta O(n), mientras que ordenar cuesta O(n log n). El enfoque con Counter es óptimo y expresa directamente la definición.
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')) # TrueGroup Anagrams (LeetCode 49)
LeetCode 49 'Group Anagrams': dada una lista de cadenas, agrupe todos los anagramas. La idea clave es que los anagramas tienen la misma secuencia de caracteres ordenada. Utilice un defaultdict(list) cuya clave sea la tupla ordenada de la cadena (las tuplas admiten hashing). Cada grupo se acumula bajo la misma clave. Tiempo: O(n × L log L), donde L es la longitud máxima de una cadena.
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())
Top K Frequent Elements (LeetCode 347)
LeetCode 347 'Top K Frequent Elements': devuelva los k elementos más frecuentes. Un enfoque directo cuesta O(n log n): cuente las frecuencias, ordénelas de forma descendente y tome los primeros k elementos. El enfoque óptimo de O(n) utiliza ordenamiento por cubetas: cree cubetas indexadas por frecuencia (de 1 a n), coloque cada elemento en la cubeta correspondiente a su frecuencia y, después, recorra las cubetas desde la frecuencia más alta hasta la más baja para recopilar 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]Sort Characters by Frequency (LeetCode 451)
LeetCode 451 'Sort Characters By Frequency': reorganice una cadena para que los caracteres aparezcan en orden descendente de frecuencia. Cuente las frecuencias, ordene los caracteres por frecuencia descendente y concaténelos. Usar most_common es el enfoque más claro en Python. Tiempo: O(n log n) para ordenar los caracteres únicos por frecuencia.
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'Task Scheduler (LeetCode 621)
LeetCode 621 'Task Scheduler': dadas unas tareas y un período de espera n, encuentre el tiempo mínimo necesario para completarlas todas. La idea clave es que la tarea más frecuente determina la estructura. Organice max_count copias de la tarea más frecuente con (n) intervalos entre ellas. El tiempo mínimo total = max((max_count - 1) * (n + 1) + num_tasks_with_max_count, total_tasks). Si hay suficientes tareas diferentes para llenar los intervalos, el tiempo de inactividad es 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)) # 10Votación por mayoría con Counter
LeetCode 169 'Majority Element': encuentre el elemento que aparece más de n/2 veces. Aunque la votación de Boyer-Moore es la solución óptima con espacio O(1), usar Counter.most_common(1) lo resuelve directamente en tiempo O(n) y espacio O(n). En entrevistas en las que se mencione el espacio O(1), presente Boyer-Moore como alternativa; si se permite espacio adicional, Counter es más claro.
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)) # 2Primer carácter no repetido
LeetCode 387 'First Unique Character in a String': encuentre el índice del primer carácter que aparece exactamente una vez. Utilice un enfoque de dos pasadas: en la primera, construya un conteo de frecuencias; en la segunda, encuentre el primer carácter cuyo conteo sea 1. Tiempo: O(n), espacio: O(1), ya que el alfabeto está limitado a 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')) # -1Subarray Sum Equals K (LeetCode 560)
LeetCode 560 'Subarray Sum Equals K': cuente los subarreglos cuya suma sea k. La fuerza bruta cuesta O(n²). El enfoque de O(n) mantiene una suma de prefijos acumulada y un mapa de frecuencias de las sumas de prefijos vistas hasta ese momento. Para cada posición i, la cantidad de subarreglos que terminan en i y cuya suma es k equivale a la cantidad de sumas de prefijos anteriores iguales a (current_prefix_sum - k). Inicialice el mapa con {0: 1} para gestionar los subarreglos que comienzan en el í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)) # 4Operaciones aritméticas e intersección de Counter
Counter admite operaciones aritméticas: + fusiona (suma los conteos), - resta (recorta en 0), & toma el mínimo (intersección) y | toma el máximo (unión). Estas operaciones simplifican problemas como «encontrar los caracteres comunes en varias cadenas» o «eliminar el mínimo número de caracteres para convertir una cadena en un anagrama de otra».
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())) # 5Resumen: cuándo usar el conteo de frecuencias
Recurra al conteo de frecuencias cuando el problema implique comprobar si dos cadenas son equivalentes salvo por el orden (anagramas), encontrar los elementos más o menos frecuentes, validar que una colección tenga los «ingredientes» correctos o convertir un problema de subarreglos o subcadenas en un problema de suma de prefijos con un mapa. La clave es que el orden dentro de un grupo no importa; solo importan las cantidades.
Utilice siempre Counter por claridad; cambie a un dict simple o a un arreglo solo cuando necesite un control más preciso o un espacio estrictamente O(1) con un alfabeto acotado.
Comprobación rápida
Ponga a prueba su comprensión de los conceptos de Data Structures & Algorithms — Coding Interview Prep de esta lección.
Repaso de la lección
En esta lección aprendió que: Counter proporciona un conteo de frecuencias O(n) con most_common, operadores aritméticos y acceso con valor cero por defecto, agrupar por forma canónica (tupla ordenada) resuelve el problema de agrupar anagramas en O(nL log L), y la suma de prefijos con un mapa de frecuencias convierte el problema de suma de subarreglo igual a k de O(n²) a O(n). A continuación abordaremos el problema de la secuencia consecutiva más larga y el diseño de cachés LRU.
Preguntas frecuentes
¿La lección «Conteo y agrupación por frecuencia» es gratis?
Sí — el texto completo de «Conteo y agrupación por frecuencia» es gratis para leer aquí en la web. Para practicarla de forma interactiva (editor de código integrado y tutor de IA 24/7) y desbloquear el resto del curso de Coding Interview Prep, actualiza a CoddyKit PRO. El curso de Coding Interview Prep incluye 4 lecciones en total.
¿Qué aprenderé en «Conteo y agrupación por frecuencia»?
Use Counter y defaultdict para contar frecuencias de caracteres, agrupe anagramas por clave ordenada y encuentre los elementos más frecuentes mediante top-k. Practicas Coding Interview Prep con código real que ejecutas directamente en el navegador, y un tutor de IA 24/7 responde tus preguntas mientras trabajas en la lección.
¿Necesito experiencia previa para empezar Coding Interview Prep?
No se requiere experiencia previa. Coding Interview Prep en CoddyKit está estructurado para principiantes hasta estudiantes avanzados, así que puedes empezar aquí o desde el inicio y avanzar a tu ritmo. Esta es la lección 3 de 4.
¿Cuánto tiempo toma la lección «Conteo y agrupación por frecuencia»?
La mayoría de las lecciones de CoddyKit toman alrededor de 5–10 minutos. Cada una es compacta e interactiva, así que avanzas constantemente y retomas exactamente por donde dejaste en la web y la app.
¿Puedo escribir y ejecutar código en esta lección de Coding Interview Prep?
Sí. Cada lección de Coding Interview Prep incluye un editor de código integrado, así que escribes y ejecutas código real directamente en tu navegador y obtienes retroalimentación instantánea de IA — sin configuración local necesaria.
Todas las lecciones de este curso
- Internals de las funciones hash y gestión de colisiones
- Two-sum y sus numerosas variantes
- Conteo y agrupación por frecuencia
- Secuencia consecutiva más larga y caché LRU