0Pricing
Coding Interview Prep · Lección

Anagramas y mapas de frecuencia de caracteres

Resuelva group-anagrams, valid-anagram y permutation-in-string mediante arrays de frecuencias y mapas hash para obtener soluciones O(n).

Anagramas y mapas de frecuencia de caracteres 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.

¿Qué es un anagrama?

Dos strings son anagramas si contienen los mismos caracteres con las mismas frecuencias, pero en un orden diferente. «listen» y «silent» son anagramas. La comprobación de corrección más sencilla consiste en ordenar ambas strings y compararlas: O(n log n). Para obtener soluciones O(n), compare mapas de frecuencias de caracteres. Los problemas de anagramas son fundamentales en las entrevistas sobre strings porque ponen a prueba varias técnicas: hashing, ordenación y arrays de frecuencias.

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

Array de frecuencias para letras minúsculas

Cuando el conjunto de caracteres está acotado (por ejemplo, solo letras minúsculas de la a a la z), sustituya el mapa hash por un array de frecuencias de tamaño 26. Indexar mediante ord(c) - ord('a') asigna «a»→0, «b»→1, ..., «z»→25. En la práctica, los arrays son más rápidos que los diccionarios gracias a la localidad de caché y a que no tienen el coste adicional del hashing. Este truco aparece en valid-anagram, anagram-permutation-in-string y palindrome-permutation.

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

Agrupar anagramas

Agrupe una lista de strings para que todos los anagramas aparezcan juntos. La solución canónica O(n×m log m) usa la string ordenada como clave de un mapa hash. Todos los anagramas producen la misma clave ordenada, por lo que terminan en el mismo grupo. Una variante O(n×m) usa una tupla de recuentos de caracteres como clave: es más lenta de calcular, pero evita ordenar por completo. Casi siempre se prefiere el enfoque de la clave ordenada por su claridad.

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']

Clave de anagrama con una tupla de recuentos

Para la variante O(n×m) de agrupación de anagramas, represente la frecuencia de cada string como una tupla de 26 recuentos: tuple(freq_array). Esto evita ordenar, pero requiere un trabajo de O(26×n×m) para construir todas las claves. Las tuplas se pueden aplicar a hashing en Python, por lo que son claves de diccionario válidas. Conviene mencionar esta variante cuando el entrevistador pida «cualquier solución O(n×m)»: demuestra que comprende las distintas ventajas y desventajas.

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']))

Elementos más frecuentes: Top K

Encuentre los k elementos más frecuentes de un array. Counter + heap: construya un mapa de frecuencias en O(n) y extraiga las k frecuencias más grandes usando un min-heap de tamaño k o Counter.most_common(k). Un enfoque de ordenación por cubetas O(n) crea cubetas indexadas por frecuencia (de 0 a n) y recopila los elementos en orden de frecuencia inverso; resulta elegante cuando k es 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 frecuencias para permutación en una string

Determine si alguna permutación de la string p aparece como subcadena de s. El mapa de frecuencias de una ventana de longitud |p| debe ser igual al mapa de frecuencias de p. A medida que la ventana se desplaza, incremente el recuento del carácter que entra y reduzca el del que sale. Comparar dos objetos Counter cuesta O(26) cada vez, por lo que el coste total es O(n×26) = O(n). Lleve la cuenta con el contador «formed» para comprobar la igualdad en 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 un anagrama

Dadas dos strings, encuentre el número mínimo de eliminaciones de caracteres necesarias para convertir una en un anagrama de la otra. Calcule los mapas de frecuencias de ambas strings; la respuesta es la suma de las diferencias absolutas de las frecuencias. Todos los caracteres presentes en una string pero ausentes en la otra deben eliminarse. Esta solución O(n) usa el patrón de combinación y diferencia aplicado a mapas de frecuencias.

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 frecuencias para Ransom Note

Compruebe si todos los caracteres de note pueden obtenerse de los caracteres de magazine (cada carácter de la revista solo se puede usar una vez). Construya un mapa de frecuencias de los caracteres de magazine y, después, reduzca el recuento por cada carácter de note. Si algún recuento se vuelve negativo, devuelva False. El tiempo es O(n + m) y el espacio es O(1) para entradas restringidas a letras minúsculas, usando un array de 26 elementos en lugar de un diccionario.

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

Hashing de subcadenas anagramas más largas

Para comprobar si dos subcadenas de una misma string son anagramas, use un hash polinómico de las frecuencias de los caracteres que sea conmutativo (independiente del orden). El XOR de los valores de los caracteres es conmutativo y se actualiza en O(1), pero tiene una alta probabilidad de colisión. Un enfoque mejor usa hashing mediante productos de primos (cada carácter se asigna a un primo distinto y el producto es independiente del orden). Es una técnica poco habitual para entrevistas avanzadas.

# 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 comprobación de patrones de mapas de frecuencias

Reconozca estos patrones de mapas de frecuencias habituales en entrevistas:

  • Anagrama válido: misma longitud + misma frecuencia → igualdad de Counter o comparación de arrays
  • Agrupar anagramas: string ordenada o tupla de frecuencias como clave de diccionario
  • Elementos más frecuentes: Top K: Counter + heap u ordenación por cubetas
  • Permutación en una string: ventana deslizante + comparación de frecuencias
  • Ransom Note: mapa de frecuencias del suministro, reducir para la demanda
  • Permutación de palíndromo: como máximo un carácter con frecuencia impar
Todo se reduce a la misma idea fundamental: la frecuencia como huella 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

Elemento único: XOR para frecuencias

XOR es una herramienta potente para problemas de frecuencias cuando exactamente un elemento aparece un número impar de veces. El XOR de un número consigo mismo se cancela y da 0: a XOR a = 0. El XOR de todos los elementos, cuando cada valor aparece un número par de veces salvo uno, deja únicamente el elemento que aparece un número impar de veces. Esto proporciona un tiempo O(n) y un espacio O(1), sin necesidad de un mapa hash. Se generaliza a la búsqueda de dos números que aparecen un número impar de veces mediante las propiedades 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'

Comprobación rápida

Compruebe su comprensión de los conceptos de Data Structures & Algorithms — Coding Interview Prep de esta lección.

Resumen de la lección

En esta lección aprendió: los mapas de frecuencias de caracteres son la herramienta fundamental para detectar anagramas, ya sea mediante un array de 26 elementos para alfabetos acotados o mediante Counter para caracteres arbitrarios, las claves de diccionario basadas en strings ordenadas o tuplas de frecuencias agrupan todos los anagramas en un tiempo O(n × m log m) u O(n × m), respectivamente, y XOR elimina limpiamente los pares en problemas con un único elemento de frecuencia impar, proporcionando un tiempo O(n) y un espacio O(1) cuando no se necesita un diccionario. A continuación exploraremos la codificación, la inversión y las técnicas de palíndromos con strings.

Preguntas frecuentes

¿La lección «Anagramas y mapas de frecuencia de caracteres» es gratis?

Sí — el texto completo de «Anagramas y mapas de frecuencia de caracteres» 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 «Anagramas y mapas de frecuencia de caracteres»?

Resuelva group-anagrams, valid-anagram y permutation-in-string mediante arrays de frecuencias y mapas hash para obtener soluciones O(n). 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 «Anagramas y mapas de frecuencia de caracteres»?

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

  1. API de strings de Python para entrevistas
  2. Ventana deslizante para subcadenas
  3. Anagramas y mapas de frecuencia de caracteres
  4. Codificación, inversión y palíndromos de strings
← Volver a Coding Interview Prep