DSA Interview Prep · Lektion

Anagrammer og tegnfrekvenskort

Løs group-anagrams, valid-anagram og permutation-in-string med frekvensarrays og hash maps for O(n)-løsninger.

Lektion 3 af 413 trin

Anagrammer og tegnfrekvenskort er en gratis DSA Interview Prep-lektion på CoddyKit. Dette er lektion 3 af 4. Du kan læse alle 3 lektioner i dette læringsspor gratis i deres fulde længde — derefter låser CoddyKit PRO alle lektioner op samt praktiske øvelser med en indbygget kodeeditor og en AI-underviser døgnet rundt. Den er en del af læringsforløbet i DSA Interview Prep, og dine fremskridt synkroniseres på tværs af nettet og CoddyKit-appen. DSA Interview Prep-kurset indeholder 4 lektioner i alt.

Hvad er et anagram

To strenge er anagrammer, hvis de indeholder de samme tegn med de samme frekvenser, blot i en anden rækkefølge. 'listen' og 'silent' er anagrammer. Det enkleste korrekthedstjek er at sortere begge strenge og sammenligne dem: O(n log n). For løsninger i O(n) kan du sammenligne frekvenskort over tegn. Anagramproblemer er standardopgaver i strengjobsamtaler, fordi de tester flere teknikker: hashberegning, sortering og frekvenstabeller.

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

Frekvenstabel for små bogstaver

Når tegnsættet er begrænset (f.eks. kun små bogstaver fra a-z), kan du erstatte en hash-tabel med en frekvenstabel med størrelse 26. Indeksering med ord(c) - ord('a') knytter 'a'→0, 'b'→1, ..., 'z'→25. Tabeller er i praksis hurtigere end ordbøger på grund af bedre cache-lokalitet og ingen ekstra omkostninger til hashing. Denne teknik bruges i problemer om gyldige anagrammer, permutationer af anagrammer i strenge og palindrompermutationer.

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

Gruppér anagrammer

Gruppér en liste med strenge, så alle anagrammer står sammen. Den almindelige O(n×m log m)-løsning bruger den sorterede streng som nøgle i en hash-tabel. Alle anagrammer giver den samme sorterede nøgle, så de havner i den samme gruppe. En variant i O(n×m) bruger en tuple med tegntællinger som nøgle — den er langsommere at beregne, men undgår sortering helt. Tilgangen med den sorterede nøgle foretrækkes næsten altid på grund af sin tydelighed.

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

Anagramnøgle med tælle-tuple

I varianten til anagramgruppering i O(n×m) repræsenterer du hver strengs frekvens som en tuple med 26 tællinger: tuple(freq_array). Det undgår sortering, men kræver O(26×n×m) arbejde for at opbygge alle nøglerne. Tupler kan hashes i Python, så de kan bruges som gyldige nøgler i en dict. Denne variant er værd at nævne, når intervieweren spørger efter 'en vilkårlig løsning i O(n×m)' — det viser, at du forstår forskellige afvejninger.

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

De K hyppigste elementer

Find de k hyppigste elementer i en tabel. Counter + heap: opbyg et frekvenskort i O(n), og udvælg derefter de k største frekvenser ved hjælp af en min-bunke med størrelse k eller Counter.most_common(k). En tilgang med bøttesortering i O(n) opretter bøtter indekseret efter frekvens (fra 0 til n) og samler elementerne i omvendt frekvensrækkefølge — elegant, når k er stor.

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]

Frekvenskort til permutation i en streng

Bestem, om en permutation af strengen p er en delstreng i s. Et frekvenskort for et vindue med længden |p| skal være lig med frekvenskortet for p. Når vinduet glider, øger du tællingen for det tegn, der kommer ind, og sænker tællingen for det tegn, der forlader vinduet. Det koster O(26) at sammenligne to Counter-objekter hver gang, hvilket giver O(n×26) = O(n) samlet. Hold styr på tælleren 'formed' for at kunne tjekke lighed i 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

Minimum antal tegnsletninger til at danne et anagram

Givet to strenge skal du finde det mindste antal tegnsletninger, der skal til for at gøre den ene til et anagram af den anden. Beregn frekvenskort for begge strenge; svaret er summen af de absolutte forskelle mellem frekvenserne. Tegn, der findes i den ene streng, men ikke i den anden, skal alle slettes. Denne løsning i O(n) bruger mønstret med sammenlægning og differens på frekvenskort.

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

Frekvenskort til løseseddel

Tjek, om alle tegn i note kan leveres af tegnene i magazine (hvert tegn i magasinet må kun bruges én gang). Opbyg et frekvenskort over tegnene i magasinet, og sænk derefter tællingen for hvert tegn i noten. Hvis en tælling bliver negativ, skal du returnere False. Det tager O(n + m) tid og O(1) plads for input, der er begrænset til små bogstaver, når du bruger en tabel med 26 elementer i stedet for en 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 af længste anagram-delstreng

Hvis du vil tjekke, om to delstrenge fra den samme streng er anagrammer, kan du bruge en polynomiel hashfunktion baseret på tegnfrekvenser, som er kommutativ (uafhængig af rækkefølgen). XOR af tegnværdier er kommutativt og kan opdateres i O(1), men har høj sandsynlighed for kollisioner. En bedre tilgang bruger hashing med primtalsprodukt (hvert tegn knyttes til et særskilt primtal, og produktet er uafhængigt af rækkefølgen). Dette er en nicheteknik til avancerede jobsamtaler.

# 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

Tjekliste over mønstre for frekvenskort

Genkend disse interviewmønstre med frekvenskort:

Gyldigt anagram: samme længde + samme frekvenser → Counter-lighed eller sammenligning af tabeller
Gruppér anagrammer: sorteret streng eller frekvens-tuple som dict-nøgle
De k hyppigste: Counter + heap eller bøttesortering
Permutation i en streng: glidende vindue + frekvenssammenligning
Løseseddel: frekvenskort over forsyningen, sænk tællingen for behovet
Palindrompermutation: højst ét tegn med en ulige tælling

Det hele reduceres til den samme grundidé: frekvens som et fingeraftryk.

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

Det enkeltstående element: XOR til frekvenser

XOR er et effektivt værktøj til frekvensproblemer, når præcis ét element forekommer et ulige antal gange. XOR af et tal med sig selv ophæver sig selv til 0: a XOR a = 0. XOR af alle elementer, hvor hver værdi forekommer et lige antal gange bortset fra én, efterlader kun den enkeltstående værdi. Det giver O(n) tid og O(1) plads — der er ikke brug for et frekvenskort. Teknikken kan generaliseres til at finde to værdier, der forekommer et ulige antal gange, ved hjælp af XOR-egenskaber.

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'

Hurtigt tjek

Tjek din forståelse af begreberne i Data Structures & Algorithms — Coding Interview Prep fra denne lektion.

Besvar den i den interaktive lektion

Lektionsopsamling

I denne lektion lærte du: frekvenskort over tegn er det vigtigste værktøj til at finde anagrammer — enten en tabel med 26 elementer for alfabeter med begrænset størrelse eller en Counter for vilkårlige tegn, nøgler baseret på sorterede strenge eller frekvens-tupler samler alle anagrammer i O(n × m log m) eller O(n × m) tid, og XOR fjerner par effektivt i problemer med ét element, der forekommer et ulige antal gange, og giver O(n) tid med O(1) plads, når der ikke er brug for en dict. Nu skal vi se på strengkodning, vending og palindromteknikker.

Gratis at komme i gang

Lær Python med en AI-underviser — gratis

Skriv og kør rigtig kode i din browser, få øjeblikkelig hjælp fra en AI-underviser døgnet rundt, og fortsæt, hvor du slap, på web eller i appen.

Kurser: 30
Lektioner: 120

Start gratis Se hele kurset

Ofte stillede spørgsmål

Er lektionen “Anagrammer og tegnfrekvenskort” gratis?

Ja — alle 3 lektioner i læringssporet DSA Interview Prep, inklusive “Anagrammer og tegnfrekvenskort”, kan læses gratis i deres fulde længde her på webstedet. Derefter låser CoddyKit PRO alle lektioner op samt interaktive øvelser med en indbygget kodeeditor og en AI-underviser døgnet rundt. DSA Interview Prep-kurset indeholder 4 lektioner i alt.

Hvad lærer jeg i “Anagrammer og tegnfrekvenskort”?

Løs group-anagrams, valid-anagram og permutation-in-string med frekvensarrays og hash maps for O(n)-løsninger. Du øver dig i DSA Interview Prep med praktisk kode, som du kører direkte i browseren, og en AI-vejleder døgnet rundt besvarer dine spørgsmål, mens du arbejder dig gennem lektionen.

Skal jeg have erfaring for at begynde på DSA Interview Prep?

Der kræves ingen tidligere erfaring. DSA Interview Prep på CoddyKit er tilrettelagt for både begyndere og øvede, så du kan starte her eller fra begyndelsen og lære i dit eget tempo. Dette er lektion 3 af 4.

Hvor lang tid tager lektionen “Anagrammer og tegnfrekvenskort”?

De fleste CoddyKit-lektioner tager cirka 5–10 minutter. Hver lektion er kort og interaktiv, så du gør løbende fremskridt og kan fortsætte, hvor du slap – på både web og app.

Kan jeg skrive og køre kode i denne DSA Interview Prep-lektion?

Ja. Alle DSA Interview Prep-lektioner har en indbygget kodeeditor, så du kan skrive og køre rigtig kode direkte i din browser og få øjeblikkelig feedback fra AI – uden lokal opsætning.

Alle lektioner i dette kursus

← Tilbage til DSA Interview Prep