字母异位词与字符频率映射
使用频率数组和哈希映射，以 O(n) 的复杂度解决字母异位词分组、有效字母异位词和字符串中的排列问题。
字母异位词与字符频率映射 是 CoddyKit 上的免费 DSA Interview Prep 课时。 这是第 3 节课，共 4 节。 你可以在下方免费阅读本课时的完整内容 — 然后在浏览器中使用内置代码编辑器和全天候 AI 导师进行实践。 这是 DSA Interview Prep 学习路径的一部分，你的进度在网页和 CoddyKit 应用中同步。 DSA Interview Prep 课程共包含 4 节课。
什么是异位词
如果两个字符串包含相同的字符，且每个字符的频率也相同，只是排列顺序不同，那么它们就是异位词。'listen' 和 'silent' 是异位词。最简单的正确性检查方法是分别对两个字符串排序并进行比较，时间复杂度为 O(n log n)。若要达到 O(n)，请比较字符频率映射。异位词问题是字符串面试中的常见题型，因为它可以检验多种技巧：哈希、排序和频率数组。
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小写字母的频率数组
当字符集有界时（例如只有小写字母 a-z），可以使用大小为 26 的频率数组替代哈希映射。通过 ord(c) - ord('a') 进行索引，可以将 'a'→0、'b'→1、……、'z'→25 映射到对应位置。由于具有更好的缓存局部性且没有哈希开销，数组在实际运行中通常比字典更快。这一技巧会出现在有效异位词、字符串中的异位词排列和回文排列问题中。
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异位词分组
请将字符串列表分组，使所有异位词彼此相邻。标准的 O(n×m log m) 解法使用排序后的字符串作为哈希映射的键。所有异位词都会生成相同的排序键，因此会进入同一个桶。O(n×m) 的变体使用字符计数元组作为键——计算速度较慢，但完全避免了排序。出于清晰性的考虑，几乎总是优先选择排序键方法。
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']使用计数元组构建异位词键
对于 O(n×m) 的异位词分组变体，请将每个字符串的频率表示为包含 26 个计数值的元组：tuple(freq_array)。这种方法避免了排序，但构建所有键需要 O(26×n×m) 的工作量。元组在 Python 中支持哈希，因此可以作为有效的字典键。当面试官要求“任意一种 O(n×m) 解法”时，值得提到这种变体——它体现了您对不同取舍的理解。
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 个元素
请找出数组中出现频率最高的 k 个元素。计数器 + 堆：在 O(n) 的时间内构建频率映射，然后使用大小为 k 的最小堆，或使用 Counter.most_common(k)，提取出现频率最高的 k 个元素。O(n) 的桶排序方法会创建按频率索引的桶（从 0 到 n），然后按频率从高到低收集元素——当 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]字符串排列的频率映射
请判断字符串 p 的任意排列是否为 s 的子字符串。长度为 |p| 的窗口的频率映射必须与 p 的频率映射相等。窗口滑动时，增加进入字符的计数，并减少离开字符的计数。每次比较两个 Counter 对象需要 O(26) 的时间，因此总体复杂度为 O(n×26) = O(n)。请跟踪“已满足”计数器，以便在 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使字符串成为异位词所需的最少字符数
给定两个字符串，请找出需要删除的最少字符数，使其中一个字符串成为另一个字符串的异位词。请分别计算两个字符串的频率映射；答案是各字符频率绝对差之和。只出现在其中一个字符串中的字符必须全部删除。这个 O(n) 的解法在频率映射上使用了“合并与差异”模式。
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赎金信的频率映射
请检查 note 中的所有字符是否都可以由 magazine 中的字符提供（每个杂志字符只能使用一次）。先构建杂志字符的频率映射；然后遍历 note 中的每个字符并减少其计数。如果任何计数变为负数，则返回假值。对于限定为小写字母的输入，使用包含 26 个元素的数组而不是字典，可以在 O(n + m) 的时间和 O(1) 的空间内完成。
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最长异位词子字符串哈希
要检查同一字符串中的两个子字符串是否为异位词，请使用字符频率的多项式哈希，这种哈希具有交换性（与顺序无关）。XOR 具有交换性，并且可以在 O(1) 的时间内更新，但发生冲突的概率较高。更好的方法是使用质数乘积哈希（将每个字符映射到不同的质数；乘积与顺序无关）。这是一种适合高级面试的冷门技巧。
# 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频率映射模式检查清单
请认识以下频率映射面试模式：
- 有效异位词：长度相同且频率相同 → 比较 Counter 是否相等，或比较数组
- 异位词分组：使用排序后的字符串或频率元组作为字典键
- 出现频率最高的前 k 个：计数器 + 堆，或桶排序
- 字符串中的排列：滑动窗口 + 频率比较
- 赎金信：建立供给字符的频率映射，再根据需求递减计数
- 回文排列：最多只能有一个字符出现奇数次
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 处理频率
当恰好有一个元素出现奇数次时，XOR 是处理频率问题的强大工具。一个数与自身进行 XOR 会抵消为 0：a XOR a = 0。将所有元素进行 XOR，若除一个值外的每个值都出现偶数次，最终结果就只会剩下那个出现奇数次的值。这样可以在 O(n) 的时间和 O(1) 的空间内完成，无需哈希映射。利用 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'快速检查
请测试您对本课数据结构与算法——编程面试准备相关概念的理解。
课程回顾
本课您学习了：字符频率映射是检测异位词的核心工具——对于有界字符集，可以使用包含 26 个元素的数组；对于任意字符，则可以使用 Counter；使用排序字符串或频率元组作为字典键，可以分别以 O(n × m log m) 或 O(n × m) 的时间将所有异位词分组；以及在单元素奇数次计数问题中，XOR 可以干净地消除成对元素；当不需要字典时，它能以 O(n) 的时间和 O(1) 的空间完成计算。接下来我们将学习字符串编码、反转和回文技巧。
常见问题解答
「字母异位词与字符频率映射」课时是免费的吗？
是的 — 「字母异位词与字符频率映射」的完整文本可在网页上免费阅读。要进行交互式练习（内置代码编辑器和全天候 AI 导师）并解锁 DSA Interview Prep 课程的其余内容，请升级到 CoddyKit PRO。 DSA Interview Prep 课程共包含 4 节课。
「字母异位词与字符频率映射」这节课中我会学到什么？
使用频率数组和哈希映射，以 O(n) 的复杂度解决字母异位词分组、有效字母异位词和字符串中的排列问题。 你通过在浏览器中直接运行的动手代码来练习 DSA Interview Prep，全天候 AI 导师会在你学习这节课的过程中回答你的问题。
学习 DSA Interview Prep 需要有经验吗？
无需任何先前经验。CoddyKit 上的 DSA Interview Prep 课程适合初学者到高级学习者，你可以从这里开始或从头开始，按照自己的节奏学习。 这是第 3 节课，共 4 节。
「字母异位词与字符频率映射」课时需要多长时间？
大多数 CoddyKit 课程大约需要 5–10 分钟。每节课都很精短且互动，所以你能稳步进步，并在网页和应用中从离开的地方继续。
我能在这节 DSA Interview Prep 课中编写并运行代码吗？
能。每节 DSA Interview Prep 课都包含内置代码编辑器，你可以在浏览器中直接编写并运行真实代码，并获得即时 AI 反馈 — 无需本地设置。
此课程中的所有课时
- 面试必备的 Python 字符串 API
- 子串的滑动窗口
- 字母异位词与字符频率映射
- 字符串编码、反转与回文