0Pricing
DSA Interview Prep · Lektion

Anagramme und Zeichenhäufigkeitskarten

Lösen Sie group-anagrams, valid-anagram und permutation-in-string mit Häufigkeits-Arrays und Hash-Maps in O(n).

Anagramme und Zeichenhäufigkeitskarten ist eine kostenlose DSA Interview Prep-Lektion auf CoddyKit. Dies ist Lektion 3 von 4. Du kannst die komplette Lektion unten kostenlos lesen – dann übst du sie direkt im Browser mit einem integrierten Code-Editor und einem KI-Tutor rund um die Uhr. Sie ist Teil des DSA Interview Prep-Lernpfads, und dein Fortschritt wird über Web und CoddyKit-App synchronisiert. Der DSA Interview Prep-Kurs umfasst insgesamt 4 Lektionen.

Was ist ein Anagramm?

Zwei Strings sind Anagramme, wenn sie dieselben Zeichen mit denselben Häufigkeiten enthalten, nur in einer anderen Reihenfolge. „listen“ und „silent“ sind Anagramme. Die einfachste Korrektheitsprüfung besteht darin, beide Strings zu sortieren und zu vergleichen: O(n log n). Für Lösungen in O(n) vergleichen Sie Häufigkeitsmaps der Zeichen. Anagramm-Probleme gehören zu den Standardaufgaben in String-Interviews, weil sie mehrere Techniken prüfen: Hashing, Sortierung und Häufigkeitsarrays.

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

Häufigkeitsarray für Kleinbuchstaben

Wenn der Zeichensatz begrenzt ist, etwa auf Kleinbuchstaben von a bis z, ersetzen Sie eine Hashmap durch ein Häufigkeitsarray der Größe 26. Die Indizierung mit ord(c) - ord('a') ordnet 'a'→0, 'b'→1, ..., 'z'→25 zu. Arrays sind in der Praxis aufgrund der Cache-Lokalität und des fehlenden Hashing-Overheads schneller als dicts. Dieser Trick kommt bei valid-anagram, anagram-permutation-in-string und palindrome-permutation zum Einsatz.

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

Anagramme gruppieren

Gruppieren Sie eine Liste von Strings so, dass alle Anagramme zusammenstehen. Die kanonische Lösung in O(n×m log m) verwendet den sortierten String als Schlüssel einer Hashmap. Alle Anagramme erzeugen denselben sortierten Schlüssel und landen daher im selben Bucket. Eine Variante in O(n×m) verwendet ein Tupel von Zeichenhäufigkeiten als Schlüssel — die Berechnung ist aufwendiger, macht eine Sortierung aber vollständig überflüssig. Der Ansatz mit dem sortierten Schlüssel wird wegen seiner Klarheit fast immer bevorzugt.

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

Anagramm-Schlüssel mit einem Zähltupel

Für die Variante zum Gruppieren von Anagrammen in O(n×m) stellen Sie die Häufigkeiten jedes Strings als Tupel aus 26 Zählwerten dar: tuple(freq_array). Dadurch entfällt die Sortierung, allerdings sind zum Erstellen aller Schlüssel O(26×n×m) Operationen erforderlich. Tupel sind in Python hashbar und daher als dict-Schlüssel gültig. Diese Variante ist erwähnenswert, wenn der Interviewer nach „einer beliebigen O(n×m)-Lösung“ fragt — sie zeigt, dass Sie die verschiedenen Abwägungen verstehen.

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

K häufigste Elemente

Finden Sie die k häufigsten Elemente in einem Array. Counter + Heap: Erstellen Sie in O(n) eine Häufigkeitsmap und ermitteln Sie anschließend die k größten Häufigkeiten mithilfe eines Min-Heaps der Größe k oder mit Counter.most_common(k). Ein Bucket-Sort-Ansatz in O(n) erstellt Buckets, die nach der Häufigkeit von 0 bis n indiziert sind, und sammelt die Elemente in umgekehrter Reihenfolge der Häufigkeit — elegant, wenn k groß ist.

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]

Häufigkeitsmap für Permutation in einem String

Bestimmen Sie, ob eine beliebige Permutation des Strings p als Teilstring in s vorkommt. Die Häufigkeitsmap eines Fensters der Länge |p| muss mit der Häufigkeitsmap von p übereinstimmen. Beim Verschieben des Fensters erhöhen Sie die Häufigkeit des hinzukommenden Zeichens und verringern die des ausscheidenden Zeichens. Der Vergleich zweier Counter-Objekte kostet jedes Mal O(26), sodass insgesamt O(n×26) = O(n) entsteht. Verfolgen Sie den Zähler „formed“, um die Gleichheit in O(1) zu prüfen.

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

Mindestanzahl an Zeichen für ein Anagramm

Gegeben sind zwei Strings. Finden Sie die minimale Anzahl von Zeichenlöschungen, die erforderlich ist, damit einer der Strings ein Anagramm des anderen wird. Berechnen Sie für beide Strings Häufigkeitsmaps. Die Antwort ist die Summe der absoluten Differenzen der Häufigkeiten. Zeichen, die nur in einem der Strings vorkommen, müssen vollständig gelöscht werden. Diese Lösung in O(n) verwendet das Muster „Zusammenführen und Differenz bilden“ für Häufigkeitsmaps.

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

Häufigkeitsmap für Ransom Note

Prüfen Sie, ob alle Zeichen in note durch Zeichen aus magazine bereitgestellt werden können, wobei jedes Zeichen aus magazine nur einmal verwendet werden darf. Erstellen Sie eine Häufigkeitsmap der Zeichen aus magazine und verringern Sie anschließend für jedes Zeichen in note den entsprechenden Zähler. Sobald ein Zähler negativ wird, geben Sie False zurück. Die Laufzeit beträgt O(n + m). Bei Eingaben, die auf Kleinbuchstaben beschränkt sind, benötigt die Lösung mit einem Array aus 26 Elementen statt einer dict O(1) Speicherplatz.

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 für längste Anagramm-Teilstrings

Um zu prüfen, ob zwei Teilstrings desselben Strings Anagramme sind, verwenden Sie einen polynomialen Hash der Zeichenhäufigkeiten, der kommutativ und damit unabhängig von der Reihenfolge ist. XOR von Zeichenwerten ist kommutativ und lässt sich in O(1) aktualisieren, hat aber eine hohe Kollisionswahrscheinlichkeit. Ein besserer Ansatz verwendet Hashing mit Primzahlprodukten: Jedes Zeichen wird auf eine eindeutige Primzahl abgebildet, und das Produkt ist unabhängig von der Reihenfolge. Dies ist eine spezielle Technik für fortgeschrittene Interviews.

# 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

Checkliste für Häufigkeitsmap-Muster

Erkennen Sie diese Häufigkeitsmap-Muster aus Interviews:

  • Gültiges Anagramm: gleiche Länge + gleiche Häufigkeiten → Counter-Gleichheit oder Array-Vergleich
  • Anagramme gruppieren: sortierter String oder Häufigkeitstupel als dict-Schlüssel
  • Top-k der häufigsten Elemente: Counter + Heap oder Bucket-Sortierung
  • Permutation in einem String: Sliding Window + Häufigkeitsvergleich
  • Ransom Note: Häufigkeitsmap des Vorrats, für den Bedarf herunterzählen
  • Palindrom-Permutation: höchstens ein Zeichen mit ungerader Häufigkeit
Alles läuft auf dieselbe grundlegende Idee hinaus: Die Häufigkeit dient als Fingerabdruck.

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

Einzelner Ausreißer: XOR für Häufigkeiten

XOR ist ein leistungsfähiges Werkzeug für Häufigkeitsprobleme, wenn genau ein Element ungerade oft vorkommt. XOR einer Zahl mit sich selbst ergibt 0: a XOR a = 0. Werden alle Elemente per XOR verknüpft und kommt jeder Wert mit Ausnahme eines einzigen eine gerade Anzahl von Malen vor, bleibt nur dieser einzelne Wert übrig. Das ergibt O(n) Laufzeit und O(1) Speicherplatz — eine Hashmap ist nicht erforderlich. Das Verfahren lässt sich mithilfe der XOR-Eigenschaften auf das Finden von zwei Werten erweitern, die ungerade oft vorkommen.

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'

Kurzer Test

Testen Sie Ihr Verständnis der Konzepte aus Data Structures & Algorithms — Coding Interview Prep, die in dieser Lektion behandelt wurden.

Zusammenfassung der Lektion

In dieser Lektion haben Sie gelernt: Häufigkeitsmaps von Zeichen sind das zentrale Werkzeug zur Erkennung von Anagrammen — entweder ein Array mit 26 Elementen für begrenzte Alphabete oder ein Counter für beliebige Zeichen, Schlüssel aus sortierten Strings oder Häufigkeitstupeln gruppieren alle Anagramme zusammen, jeweils in O(n × m log m) beziehungsweise O(n × m) und XOR eliminiert Paare bei Problemen mit einem einzelnen Element ungerader Häufigkeit zuverlässig und ermöglicht O(n) Laufzeit bei O(1) Speicherplatz, wenn keine dict benötigt wird. Als Nächstes sehen Sie sich String-Kodierung, Umkehrung und Palindromtechniken an.

Häufig gestellte Fragen

Ist die Lektion „Anagramme und Zeichenhäufigkeitskarten“ kostenlos?

Ja — der vollständige Text von „Anagramme und Zeichenhäufigkeitskarten“ ist hier im Web kostenlos zu lesen. Um sie interaktiv zu üben (integrierter Code-Editor und 24/7 KI-Tutor) und den Rest des DSA Interview Prep-Kurses freizuschalten, upgrade auf CoddyKit PRO. Der DSA Interview Prep-Kurs umfasst insgesamt 4 Lektionen.

Was lerne ich in „Anagramme und Zeichenhäufigkeitskarten“?

Lösen Sie group-anagrams, valid-anagram und permutation-in-string mit Häufigkeits-Arrays und Hash-Maps in O(n). Du übst DSA Interview Prep mit praktischem Code, den du direkt im Browser ausführst, und ein 24/7 KI-Tutor beantwortet deine Fragen während du die Lektion bearbeitest.

Brauche ich Erfahrung, um DSA Interview Prep zu starten?

Keine Vorkenntnisse erforderlich. DSA Interview Prep auf CoddyKit ist für Anfänger bis fortgeschrittene Lernende strukturiert, sodass du hier starten oder von Anfang an beginnen und in deinem eigenen Tempo voranschreiten kannst. Dies ist Lektion 3 von 4.

Wie lange dauert die Lektion „Anagramme und Zeichenhäufigkeitskarten“?

Die meisten CoddyKit-Lektionen dauern etwa 5–10 Minuten. Jede ist kompakt und interaktiv, sodass du stetig Fortschritte machst und genau dort weitermachst, wo du aufgehört hast – im Web und in der App.

Kann ich in dieser DSA Interview Prep-Lektion Code schreiben und ausführen?

Ja. Jede DSA Interview Prep-Lektion enthält einen integrierten Code-Editor, sodass du echten Code direkt in deinem Browser schreibst und ausführst und sofort KI-Feedback erhältst — ohne lokale Einrichtung erforderlich.

Alle Lektionen in diesem Kurs

  1. Python-String-API für Interviews
  2. Sliding Window für Teilstrings
  3. Anagramme und Zeichenhäufigkeitskarten
  4. String-Kodierung, Umkehrung und Palindrome
← Zurück zu DSA Interview Prep