0Pricing
Coding Interview Prep · Lekcja

Anagramy i mapy częstotliwości znaków

Rozwiążą Państwo zadania group-anagrams, valid-anagram i permutation-in-string, korzystając z tablic częstotliwości i map haszujących, aby uzyskać rozwiązania w O(n).

Anagramy i mapy częstotliwości znaków to bezpłatna lekcja Coding Interview Prep na CoddyKit. To lekcja 3 z 4. Możesz przeczytać całą lekcję poniżej za darmo — a potem ćwiczyć ją interaktywnie w przeglądarce z wbudowanym edytorem kodu i tutorem AI dostępnym 24/7. To część ścieżki edukacyjnej Coding Interview Prep, a Twój postęp synchronizuje się między webem a aplikacją CoddyKit. Kurs Coding Interview Prep zawiera 4 lekcji w sumie.

Czym jest anagram?

Dwa łańcuchy znaków są anagramami, jeśli zawierają te same znaki z takimi samymi częstościami, ale w innej kolejności. 'listen' i 'silent' są anagramami. Najprostsze sprawdzenie poprawności polega na posortowaniu obu łańcuchów i ich porównaniu, co kosztuje O(n log n). Aby uzyskać rozwiązanie O(n), należy porównać mapy częstości znaków. Problemy z anagramami są stałym elementem rozmów kwalifikacyjnych dotyczących programowania, ponieważ sprawdzają kilka technik: haszowanie, sortowanie i tablice częstości.

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

Tablica częstości dla małych liter

Gdy zbiór znaków jest ograniczony (np. obejmuje wyłącznie małe litery a-z), mapę haszującą można zastąpić tablicą częstości o rozmiarze 26. Indeksowanie za pomocą ord(c) - ord('a') odwzorowuje 'a'→0, 'b'→1, ..., 'z'→25. Tablice są w praktyce szybsze niż słowniki dzięki lokalności pamięci podręcznej i brakowi narzutu haszowania. Ta sztuczka pojawia się w problemach valid-anagram, anagram-permutation-in-string i 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

Grupowanie anagramów

Należy pogrupować listę łańcuchów znaków tak, aby wszystkie anagramy znalazły się obok siebie. Kanoniczne rozwiązanie O(n×m log m) używa posortowanego łańcucha jako klucza mapy haszującej. Wszystkie anagramy tworzą ten sam posortowany klucz, więc trafiają do tego samego kubełka. Wariant O(n×m) używa jako klucza krotki liczności znaków — jej utworzenie jest wolniejsze, ale pozwala całkowicie uniknąć sortowania. Podejście z posortowanym kluczem jest niemal zawsze preferowane ze względu na czytelność.

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

Klucz anagramu z krotką liczności

W wariancie grupowania anagramów O(n×m) częstość znaków każdego łańcucha należy reprezentować jako krotkę 26 liczności: tuple(freq_array). Pozwala to uniknąć sortowania, ale wymaga O(26×n×m) operacji na utworzenie wszystkich kluczy. Krotki można haszować w Pythonie, dzięki czemu mogą być poprawnymi kluczami słownika. Warto wspomnieć o tym wariancie, gdy osoba przeprowadzająca rozmowę poprosi o „dowolne rozwiązanie O(n×m)” — pokazuje to znajomość różnych kompromisów.

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 najczęściej występujących elementów

Należy znaleźć k najczęściej występujących elementów w tablicy. Counter + kopiec: najpierw budujemy mapę częstości w czasie O(n), a następnie wybieramy k największych częstości za pomocą kopca minimalnego o rozmiarze k lub Counter.most_common(k). Podejście O(n) z użyciem sortowania kubełkowego tworzy kubełki indeksowane częstością (od 0 do n), a następnie zbiera elementy w odwrotnej kolejności częstości — jest eleganckie, gdy k jest duże.

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 częstości dla permutacji w łańcuchu

Należy ustalić, czy dowolna permutacja łańcucha p jest podłańcuchem s. Mapa częstości okna o długości |p| musi być równa mapie częstości p. Podczas przesuwania okna należy zwiększać liczność znaku wchodzącego do okna i zmniejszać liczność znaku, który je opuszcza. Porównywanie dwóch obiektów Counter za każdym razem kosztuje O(26), co daje łącznie O(n×26) = O(n). Należy śledzić licznik „formed”, aby sprawdzać równość w czasie 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

Minimalna liczba znaków potrzebna do utworzenia anagramu

Dla dwóch łańcuchów znaków należy znaleźć minimalną liczbę usunięć znaków potrzebnych, aby jeden z nich stał się anagramem drugiego. Należy obliczyć mapy częstości dla obu łańcuchów; wynikiem jest suma wartości bezwzględnych różnic częstości. Wszystkie znaki występujące w jednym łańcuchu, a nieobecne w drugim, muszą zostać usunięte. To rozwiązanie O(n) wykorzystuje wzorzec „merge and diff” dla map częstości.

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 częstości dla notatki

Należy sprawdzić, czy wszystkie znaki w note mogą zostać dostarczone przez znaki w magazine (każdego znaku z magazine można użyć tylko raz). Proszę zbudować mapę częstości znaków z magazine, a następnie dla każdego znaku w note zmniejszyć jego liczność. Jeśli któraś liczność spadnie poniżej zera, należy zwrócić False. Czas działania wynosi O(n + m), a pamięć O(1) dla danych wejściowych ograniczonych do małych liter, gdy zamiast słownika używana jest tablica 26 elementów.

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

Haszowanie najdłuższych anagramowych podłańcuchów

Aby sprawdzić, czy dwa podłańcuchy tego samego łańcucha są anagramami, należy użyć hasza wielomianowego częstości znaków, który jest przemienny (niezależny od kolejności). XOR wartości znaków jest przemienny i można go aktualizować w czasie O(1), ale charakteryzuje się wysokim prawdopodobieństwem kolizji. Lepsze podejście wykorzystuje haszowanie iloczynem liczb pierwszych (każdy znak jest odwzorowany na inną liczbę pierwszą, a iloczyn jest niezależny od kolejności). Jest to niszowa technika przeznaczona do zaawansowanych rozmów kwalifikacyjnych.

# 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 kontrolna wzorców map częstości

Proszę rozpoznać następujące wzorce zadań rekrutacyjnych opartych na mapach częstości:

  • Valid anagram: ta sama długość + ta sama częstość → równość Counter lub porównanie tablic
  • Group anagrams: posortowany łańcuch lub krotka częstości jako klucz słownika
  • Top-k frequent: Counter + kopiec lub sortowanie kubełkowe
  • Permutation in string: przesuwne okno + porównanie częstości
  • Ransom note: mapa częstości zasobów, zmniejszana dla zapotrzebowania
  • Palindrome permutation: co najwyżej jeden znak występujący nieparzystą liczbę razy
Każdy z tych problemów sprowadza się do tej samej podstawowej idei: częstość jako odcisk palca.

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

Element odstający: XOR do zliczania częstości

XOR jest potężnym narzędziem w problemach dotyczących częstości, gdy dokładnie jeden element występuje nieparzystą liczbę razy. XOR liczby z nią samą daje 0: a XOR a = 0. XOR wszystkich elementów, gdy każda wartość poza jedną występuje parzystą liczbę razy, pozostawia wyłącznie tę nieparzystą wartość. Daje to czas O(n) i pamięć O(1) — mapa haszująca nie jest potrzebna. Można uogólnić tę metodę na znajdowanie dwóch liczb występujących nieparzystą liczbę razy, wykorzystując właściwości 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'

Szybki test

Proszę sprawdzić znajomość koncepcji przedstawionych w tej lekcji w ramach Data Structures & Algorithms — Coding Interview Prep.

Podsumowanie lekcji

W tej lekcji poznali Państwo: mapy częstości znaków są podstawowym narzędziem wykrywania anagramów — można użyć tablicy 26 elementów dla ograniczonych alfabetów albo obiektu Counter dla dowolnych znaków, klucze słownika będące posortowanym łańcuchem lub krotką częstości grupują wszystkie anagramy razem, odpowiednio w czasie O(n × m log m) lub O(n × m), oraz XOR skutecznie eliminuje pary w problemach z pojedynczym elementem występującym nieparzystą liczbę razy, zapewniając czas O(n) i pamięć O(1), gdy słownik nie jest potrzebny. W następnej lekcji omówimy kodowanie i odwracanie łańcuchów znaków oraz techniki dotyczące palindromów.

Często zadawane pytania

Czy lekcja „Anagramy i mapy częstotliwości znaków” jest bezpłatna?

Tak — pełny tekst „Anagramy i mapy częstotliwości znaków” jest dostępny za darmo tutaj w sieci. Aby ćwiczyć ją interaktywnie (wbudowany edytor kodu i tutor AI dostępny 24/7) i odblokować resztę kursu Coding Interview Prep, przejdź na CoddyKit PRO. Kurs Coding Interview Prep zawiera 4 lekcji w sumie.

Co nauczysz się w „Anagramy i mapy częstotliwości znaków”?

Rozwiążą Państwo zadania group-anagrams, valid-anagram i permutation-in-string, korzystając z tablic częstotliwości i map haszujących, aby uzyskać rozwiązania w O(n). Ćwiczysz Coding Interview Prep z praktycznym kodem, który uruchamiasz bezpośrednio w przeglądarce, a tutor AI dostępny 24/7 odpowiada na Twoje pytania podczas pracy nad lekcją.

Czy potrzebuję doświadczenia, aby zacząć Coding Interview Prep?

Nie wymagamy żadnego doświadczenia. Coding Interview Prep w CoddyKit jest strukturyzowany dla początkujących i zaawansowanych użytkowników, więc możesz zacząć tutaj lub od początku i uczyć się w swoim tempie. To lekcja 3 z 4.

Ile czasu zajmuje lekcja „Anagramy i mapy częstotliwości znaków”?

Większość lekcji CoddyKit trwa około 5–10 minut. Każda lekcja to mały, interaktywny krok, dzięki czemu robisz systematyczne postępy i zawsze wracasz dokładnie do tego samego miejsca — na webie i w aplikacji.

Czy mogę pisać i uruchamiać kod w tej lekcji Coding Interview Prep?

Tak. Każda lekcja Coding Interview Prep zawiera wbudowany edytor kodu, więc piszesz i uruchamiasz prawdziwy kod bezpośrednio w przeglądarce i od razu otrzymujesz sprzężenie zwrotne od AI — bez konfiguracji na komputerze.

Wszystkie lekcje w tym kursie

  1. Python String API na rozmowach rekrutacyjnych
  2. Okno przesuwne dla podciągów
  3. Anagramy i mapy częstotliwości znaków
  4. Kodowanie ciągów, odwracanie i palindromy
← Powrót do Coding Interview Prep