Анаграммы и карты частот символов

Что такое анаграмма

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

Массив частот для строчных букв

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

Группировка анаграмм

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

Ключ анаграммы с кортежем количеств

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 наиболее частых элементов

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]

Карта частот для перестановки в строке

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

Минимальное число символов для создания анаграммы

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

Карта частот для записки о выкупе

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

Хеширование самой длинной анаграммной подстроки

# 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

Памятка по шаблонам карт частот

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

Единственный непарный элемент: 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'

Быстрая проверка

Итоги урока