0Pricing
DSA Interview Prep · Lezione

Anagrammi e mappe delle frequenze dei caratteri

Risolva group-anagrams, valid-anagram e permutation-in-string usando array di frequenze e hash map per ottenere soluzioni O(n)

Anagrammi e mappe delle frequenze dei caratteri è una lezione DSA Interview Prep gratuita su CoddyKit. Questa è la lezione 3 di 4. Puoi leggere la lezione completa qui gratuitamente — poi esercitati direttamente nel browser con un editor di codice integrato e un tutor IA disponibile 24/7. Fa parte del percorso di apprendimento DSA Interview Prep, e i tuoi progressi si sincronizzano tra il web e l'app CoddyKit. Il corso DSA Interview Prep include 4 lezioni in totale.

Che cos'è un anagramma

Due stringhe sono anagrammi se contengono gli stessi caratteri con le stesse frequenze, ma in un ordine diverso. 'listen' e 'silent' sono anagrammi. Il controllo di correttezza più semplice consiste nell'ordinare entrambe le stringhe e confrontarle: O(n log n). Per ottenere soluzioni O(n), confronti le mappe delle frequenze dei caratteri. I problemi sugli anagrammi sono un classico dei colloqui sulle stringhe perché verificano diverse tecniche: hashing, ordinamento e array di frequenze.

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 delle frequenze per le lettere minuscole

Quando l'insieme di caratteri è limitato (ad esempio, solo le lettere minuscole da a a z), sostituisca una hash map con un array delle frequenze di dimensione 26. L'indicizzazione tramite ord(c) - ord('a') associa 'a'→0, 'b'→1, ..., 'z'→25. Nella pratica gli array sono più veloci dei dict grazie alla località della cache e all'assenza del sovraccarico dell'hashing. Questo trucco compare nei problemi valid-anagram, anagram-permutation-in-string e 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

Raggruppare gli anagrammi

Raggruppi un elenco di stringhe in modo che tutti gli anagrammi compaiano insieme. La soluzione canonica O(n×m log m) utilizza la stringa ordinata come chiave di una hash map. Tutti gli anagrammi producono la stessa chiave ordinata e finiscono quindi nello stesso bucket. Una variante O(n×m) utilizza come chiave una tupla dei conteggi dei caratteri: è più lenta da calcolare, ma evita completamente l'ordinamento. Per chiarezza, si preferisce quasi sempre l'approccio basato sulla chiave ordinata.

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

Chiave per gli anagrammi con tupla dei conteggi

Nella variante O(n×m) del raggruppamento degli anagrammi, rappresenti la frequenza di ogni stringa con una tupla di 26 conteggi: tuple(freq_array). In questo modo evita l'ordinamento, ma deve eseguire O(26×n×m) operazioni per costruire tutte le chiavi. In Python le tuple sono hashable, quindi possono essere usate come chiavi di dict. Vale la pena citare questa variante quando l'intervistatore chiede «una soluzione O(n×m) qualsiasi»: dimostra che comprende i diversi compromessi.

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

Elementi più frequenti: primi K

Trovi i k elementi più frequenti in un array. Counter + heap: costruisca una mappa delle frequenze in O(n), quindi estragga le k frequenze più alte utilizzando un min-heap di dimensione k o Counter.most_common(k). Un approccio O(n) con bucket sort crea bucket indicizzati per frequenza (da 0 a n) e raccoglie gli elementi in ordine di frequenza decrescente: è 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]

Mappa delle frequenze per la permutazione in una stringa

Determini se una qualsiasi permutazione della stringa p è presente come sottostringa di s. La mappa delle frequenze di una finestra di lunghezza |p| deve essere uguale alla mappa delle frequenze di p. Mentre la finestra scorre, incrementi il conteggio del carattere che entra e decrementi quello del carattere che esce. Confrontare due oggetti Counter costa O(26) ogni volta, quindi il costo complessivo è O(n×26) = O(n). Tenga traccia del contatore 'formed' per verificare l'uguaglianza in 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

Numero minimo di caratteri per creare un anagramma

Date due stringhe, trovi il numero minimo di caratteri da eliminare per rendere una stringa un anagramma dell'altra. Calcoli le mappe delle frequenze per entrambe le stringhe; la risposta è la somma delle differenze assolute tra le frequenze. Tutti i caratteri presenti in una stringa ma assenti nell'altra devono essere eliminati. Questa soluzione O(n) utilizza lo schema «merge and diff» sulle mappe delle frequenze.

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

Mappa delle frequenze per Ransom Note

Verifichi se tutti i caratteri presenti in note possono essere forniti dai caratteri presenti in magazine (ogni carattere della rivista può essere usato una sola volta). Costruisca una mappa delle frequenze dei caratteri di magazine; quindi, per ogni carattere di note, decrementi il conteggio. Se un conteggio diventa negativo, restituisca False. Il tempo è O(n + m) e lo spazio è O(1) per input limitati alle lettere minuscole, utilizzando un array di 26 elementi invece di un dict.

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 delle sottostringhe anagramme più lunghe

Per verificare se due sottostringhe della stessa stringa sono anagrammi, utilizzi un hash polinomiale delle frequenze dei caratteri che sia commutativo, cioè indipendente dall'ordine. Lo XOR dei valori dei caratteri è commutativo e si aggiorna in O(1), ma presenta un'elevata probabilità di collisione. Un approccio migliore utilizza l'hashing basato sul prodotto di numeri primi (a ogni carattere corrisponde un primo distinto; il prodotto è indipendente dall'ordine). È una tecnica di nicchia per colloqui tecnici avanzati.

# 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

Checklist degli schemi con mappe delle frequenze

Riconosca questi schemi con mappe delle frequenze ricorrenti nei colloqui:

  • Anagramma valido: stessa lunghezza + stessa frequenza → uguaglianza tra Counter o confronto tra array
  • Raggruppamento degli anagrammi: stringa ordinata o tupla delle frequenze come chiave di dict
  • Elementi più frequenti: Counter + heap o bucket sort
  • Permutazione in una stringa: finestra scorrevole + confronto delle frequenze
  • Ransom note: mappa delle frequenze della disponibilità, decrementata per la richiesta
  • Permutazione palindroma: al massimo un carattere con conteggio dispari
Tutto si riduce alla stessa idea fondamentale: la frequenza come impronta digitale.

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 spaiato: XOR per le frequenze

XOR è uno strumento potente per i problemi sulle frequenze quando esattamente un elemento compare un numero dispari di volte. Lo XOR di un numero con sé stesso si annulla e diventa 0: a XOR a = 0. Applicando XOR a tutti gli elementi, quando ogni valore compare un numero pari di volte tranne uno, rimane solo quello con conteggio dispari. Si ottengono così tempo O(n) e spazio O(1), senza bisogno di una hash map. Il metodo si generalizza alla ricerca di due numeri con conteggio dispari sfruttando le proprietà di 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 rapida

Verifichi la Sua comprensione dei concetti di Data Structures & Algorithms — Coding Interview Prep presentati in questa lezione.

Riepilogo della lezione

In questa lezione ha imparato che: le mappe delle frequenze dei caratteri sono lo strumento fondamentale per rilevare gli anagrammi: si utilizza un array di 26 elementi per gli alfabeti limitati oppure un Counter per i caratteri arbitrari, le chiavi di dict basate su stringhe ordinate o tuple delle frequenze raggruppano tutti gli anagrammi rispettivamente in O(n × m log m) o O(n × m) e XOR elimina le coppie in modo efficace nei problemi con un singolo elemento dal conteggio dispari, fornendo tempo O(n) e spazio O(1) quando non è necessario alcun dict. Prossimamente esploreremo la codifica e l'inversione delle stringhe e le tecniche per i palindromi.

Domande Frequenti

La lezione «Anagrammi e mappe delle frequenze dei caratteri» è gratuita?

Sì — il testo completo di «Anagrammi e mappe delle frequenze dei caratteri» è gratuito qui sul web. Per esercitarvi in modo interattivo (un editor di codice integrato e un tutor IA 24/7) e sbloccare il resto del corso DSA Interview Prep, passa a CoddyKit PRO. Il corso DSA Interview Prep include 4 lezioni in totale.

Cosa imparerò in «Anagrammi e mappe delle frequenze dei caratteri»?

Risolva group-anagrams, valid-anagram e permutation-in-string usando array di frequenze e hash map per ottenere soluzioni O(n) Eserciti DSA Interview Prep con codice pratico che esegui direttamente nel browser, e un tutor IA 24/7 risponde alle tue domande mentre lavori sulla lezione.

Ho bisogno di esperienza per iniziare DSA Interview Prep?

Non è richiesta alcuna esperienza precedente. DSA Interview Prep su CoddyKit è strutturato per principianti e studenti avanzati, quindi puoi iniziare da qui o dall'inizio e procedere al tuo ritmo. Questa è la lezione 3 di 4.

Quanto tempo richiede la lezione «Anagrammi e mappe delle frequenze dei caratteri»?

La maggior parte delle lezioni CoddyKit richiede circa 5–10 minuti. Ogni lezione è breve e interattiva, quindi fai progressi costanti e riprendi esattamente da dove hai lasciato su web e app.

Posso scrivere ed eseguire codice in questa lezione DSA Interview Prep?

Sì. Ogni lezione DSA Interview Prep include un editor di codice integrato, quindi scrivi ed esegui codice reale direttamente nel tuo browser e ricevi feedback istantaneo dall'IA — nessuna configurazione locale necessaria.

Tutte le lezioni di questo corso

  1. API delle stringhe Python per i colloqui
  2. Sliding window per le sottostringhe
  3. Anagrammi e mappe delle frequenze dei caratteri
  4. Codifica, inversione e palindromi delle stringhe
← Torna a DSA Interview Prep