0Pricing
Coding Interview Prep · Leçon

Anagrammes et tables de fréquences de caractères

Résolvez group-anagrams, valid-anagram et permutation-in-string à l’aide de tableaux de fréquences et de tables de hachage pour obtenir des solutions en O(n).

Anagrammes et tables de fréquences de caractères est une leçon Coding Interview Prep gratuite sur CoddyKit. Ceci est la leçon 3 sur 4. Tu peux lire la leçon complète ci-dessous gratuitement — puis la pratiquer en direct dans le navigateur avec un éditeur de code intégré et un tuteur IA 24/7. Elle fait partie du parcours d'apprentissage Coding Interview Prep, et ta progression se synchronise sur le web et l'application CoddyKit. Le cours Coding Interview Prep comprend 4 leçons au total.

Qu'est-ce qu'un anagramme ?

Deux chaînes sont des anagrammes si elles contiennent les mêmes caractères avec les mêmes fréquences, mais dans un ordre différent. 'listen' et 'silent' sont des anagrammes. La vérification de correction la plus simple consiste à trier les deux chaînes et à les comparer : O(n log n). Pour obtenir des solutions en O(n), comparez les tables de fréquences des caractères. Les problèmes d'anagrammes sont incontournables dans les entretiens sur les chaînes, car ils évaluent plusieurs techniques : hachage, tri et tableaux de fréquences.

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

Tableau de fréquences pour les lettres minuscules

Lorsque l'ensemble de caractères est borné (par exemple, uniquement les minuscules de a à z), remplacez une table de hachage par un tableau de fréquences de taille 26. L'indexation par ord(c) - ord('a') associe 'a'→0, 'b'→1, ..., 'z'→25. En pratique, les tableaux sont plus rapides que les dictionnaires grâce à la localité du cache et à l'absence de coût de hachage. Cette astuce apparaît dans les problèmes d'anagramme valide, de permutation d'anagramme dans une chaîne et de permutation de palindrome.

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

Regrouper les anagrammes

Regroupez une liste de chaînes de sorte que tous les anagrammes apparaissent ensemble. La solution canonique en O(n×m log m) utilise la chaîne triée comme clé d'une table de hachage. Tous les anagrammes produisent la même clé triée et se retrouvent donc dans le même compartiment. Une variante en O(n×m) utilise un tuple de comptes de caractères comme clé — plus lente à calculer, mais qui évite entièrement le tri. L'approche fondée sur la clé triée est presque toujours préférable pour sa clarté.

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

Clé d'anagramme avec un tuple de comptes

Pour la variante du regroupement d'anagrammes en O(n×m), représentez la fréquence de chaque chaîne par un tuple de 26 comptes : tuple(freq_array). Cela évite le tri, mais nécessite O(26×n×m) opérations pour construire toutes les clés. Les tuples peuvent être hachés en Python, ce qui en fait des clés de dictionnaire valides. Cette variante mérite d'être mentionnée lorsque l'intervieweur demande « n'importe quelle solution en O(n×m) » : elle montre que vous comprenez les différents compromis.

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

Éléments les plus fréquents : top K

Trouvez les k éléments les plus fréquents d'un tableau. Compteur et tas : construisez une table de fréquences en O(n), puis extrayez les k fréquences les plus élevées à l'aide d'un tas-min de taille k ou de Counter.most_common(k). Une approche par tri en compartiments en O(n) crée des compartiments indexés par fréquence (de 0 à n), puis collecte les éléments dans l'ordre décroissant des fréquences — une méthode élégante lorsque k est grand.

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]

Table de fréquences pour la permutation dans une chaîne

Déterminez si une permutation de la chaîne p est une sous-chaîne de s. La table de fréquences d'une fenêtre de longueur |p| doit être égale à celle de p. Lorsque la fenêtre glisse, incrémentez le compte du caractère entrant et décrémentez celui du caractère sortant. Comparer deux objets Counter coûte O(26) à chaque fois, soit O(n×26) = O(n) au total. Suivez le compteur « formed » pour effectuer une vérification d'égalité 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

Nombre minimal de caractères pour former un anagramme

Étant données deux chaînes, trouvez le nombre minimal de suppressions de caractères nécessaires pour transformer l'une en anagramme de l'autre. Calculez les tables de fréquences des deux chaînes ; la réponse est la somme des différences absolues entre les fréquences. Tous les caractères présents dans l'une mais absents de l'autre doivent être supprimés. Cette solution en O(n) utilise le modèle « fusion et différence » appliqué aux tables de fréquences.

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

Table de fréquences pour la note de rançon

Vérifiez si tous les caractères de note peuvent être fournis par les caractères de magazine (chaque caractère du magazine ne peut être utilisé qu'une seule fois). Construisez une table de fréquences des caractères du magazine, puis décrémentez le compte pour chaque caractère de la note. Si un compte devient négatif, renvoyez False. La complexité temporelle est O(n + m) et l'espace utilisé est O(1) pour des entrées limitées aux lettres minuscules, en utilisant un tableau de 26 éléments au lieu d'un dictionnaire.

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

Hachage des plus longues sous-chaînes anagrammes

Pour vérifier si deux sous-chaînes d'une même chaîne sont des anagrammes, utilisez un hachage polynomial des fréquences de caractères, commutatif (indépendant de l'ordre). Le XOR des valeurs de caractères est commutatif et se met à jour en O(1), mais sa probabilité de collision est élevée. Une meilleure approche utilise un hachage par produit de nombres premiers (chaque caractère est associé à un nombre premier distinct ; le produit est indépendant de l'ordre). Il s'agit d'une technique spécialisée destinée aux entretiens avancés.

# 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

Liste de vérification des modèles de tables de fréquences

Reconnaissez ces modèles d'entretien fondés sur les tables de fréquences :

  • Anagramme valide : même longueur + mêmes fréquences → égalité de compteurs ou comparaison de tableaux
  • Regroupement d'anagrammes : chaîne triée ou tuple de fréquences comme clé de dictionnaire
  • Éléments les plus fréquents : compteur et tas, ou tri en compartiments
  • Permutation dans une chaîne : fenêtre glissante et comparaison des fréquences
  • Note de rançon : table de fréquences des caractères disponibles, décrémentée selon la demande
  • Permutation de palindrome : au plus un caractère dont le compte est impair
Tout se réduit à la même idée fondamentale : la fréquence comme empreinte.

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

L'élément différent : XOR pour les fréquences

XOR est un outil puissant pour les problèmes de fréquences lorsqu'un seul élément est présent un nombre impair de fois. Le XOR d'un nombre avec lui-même s'annule pour donner 0 : a XOR a = 0. Le XOR de tous les éléments, lorsque chaque valeur apparaît un nombre pair de fois sauf une, ne laisse que l'élément apparaissant un nombre impair de fois. Cela donne une complexité temporelle de O(n) et un espace utilisé de O(1), sans table de hachage. Cette technique se généralise à la recherche de deux nombres apparaissant un nombre impair de fois grâce aux propriétés 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'

Vérification rapide

Vérifiez votre compréhension des concepts de Structures de données et algorithmes — préparation aux entretiens de programmation présentés dans cette leçon.

Récapitulatif de la leçon

Dans cette leçon, vous avez appris que : les tables de fréquences de caractères sont l'outil fondamental pour détecter les anagrammes — soit un tableau de 26 éléments pour les alphabets bornés, soit un compteur pour les caractères arbitraires, les clés de dictionnaire fondées sur une chaîne triée ou un tuple de fréquences regroupent tous les anagrammes en O(n × m log m) ou O(n × m) respectivement, et XOR élimine proprement les paires pour les problèmes où un seul élément apparaît un nombre impair de fois, avec une complexité temporelle de O(n) et un espace utilisé de O(1) lorsqu'aucun dictionnaire n'est nécessaire. Nous allons maintenant étudier l'encodage des chaînes, leur inversion et les techniques liées aux palindromes.

Questions Fréquemment Posées

La leçon « Anagrammes et tables de fréquences de caractères » est-elle gratuite ?

Oui — le texte complet de « Anagrammes et tables de fréquences de caractères » est gratuit à lire ici sur le web. Pour la pratiquer de manière interactive (un éditeur de code intégré et un tuteur IA 24/7) et déverrouiller le reste du cours Coding Interview Prep, passe à CoddyKit PRO. Le cours Coding Interview Prep comprend 4 leçons au total.

Qu'est-ce que j'apprendrai dans « Anagrammes et tables de fréquences de caractères » ?

Résolvez group-anagrams, valid-anagram et permutation-in-string à l’aide de tableaux de fréquences et de tables de hachage pour obtenir des solutions en O(n). Tu pratiques Coding Interview Prep avec du code pratique que tu exécutes directement dans le navigateur, et un tuteur IA 24/7 répond à tes questions au fur et à mesure que tu avances dans la leçon.

Dois-je avoir de l'expérience pour commencer Coding Interview Prep ?

Aucune expérience préalable n'est requise. Coding Interview Prep sur CoddyKit est structuré pour les débutants jusqu'aux apprenants avancés, donc tu peux commencer ici ou depuis le début et avancer à ton rythme. Ceci est la leçon 3 sur 4.

Combien de temps prend la leçon « Anagrammes et tables de fréquences de caractères » ?

La plupart des leçons CoddyKit prennent environ 5–10 minutes. Chacune est courte et interactive, tu progresses régulièrement et tu repiques exactement où tu t'es arrêté sur le web et l'app.

Peux-tu écrire et exécuter du code dans cette leçon Coding Interview Prep ?

Oui. Chaque leçon Coding Interview Prep inclut un éditeur de code intégré, tu écris et exécutes du vrai code directement dans ton navigateur et tu reçois des retours IA instantanés — aucune configuration locale requise.

Toutes les leçons de ce cours

  1. API des chaînes Python pour les entretiens
  2. Fenêtre glissante pour les sous-chaînes
  3. Anagrammes et tables de fréquences de caractères
  4. Codage, inversion et palindromes de chaînes
← Retour à Coding Interview Prep