頻度カウントとグループ化
Counterとdefaultdictで文字頻度を数え、ソートしたキーでアナグラムをグループ化し、出現頻度上位k個の要素を見つけます。
「頻度カウントとグループ化」はCoddyKit上の無料Coding Interview Prepレッスンです。 これはレッスン3/4です。 下記で完全なレッスンを無料で読むことができます。その後、ブラウザ内の組み込みコードエディタと24時間対応のAIチューターでハンズオン演習できます。 これはCoding Interview Prep学習パスの一部であり、ウェブとCoddyKitアプリ全体で進捗が同期されます。 Coding Interview Prepコースには全4レッスンが含まれています。
頻度カウント：基本パターン
頻度カウントは、コーディング面接で最も応用範囲の広いパターンの一つです。リストや文字列に各要素が何回現れるかを数えることで、重複、アナグラム、最頻出要素、有効な並べ方などに関する問題を O(n) 時間で解決できます。これは、ソートしてから走査する O(n log n) の方法よりも大幅に効率的です。
Python では Counter と defaultdict(int) が標準的なツールです。どちらも要素から個数へのマッピングを作成しますが、Counter はさらに算術演算と most_common をサポートします。
from collections import Counter
words = ['apple', 'banana', 'apple', 'cherry', 'banana', 'apple']
freq = Counter(words)
print(freq) # Counter({'apple':3,'banana':2,'cherry':1})
print(freq['apple']) # 3
print(freq['grape']) # 0 (not KeyError)
print(freq.most_common(2)) # [('apple',3),('banana',2)]有効なアナグラム（LeetCode 242）
LeetCode 242「有効なアナグラム」では、2つの文字列が互いにアナグラムかどうかを判定します。2つの文字列がアナグラムであるとは、各文字の出現回数が同じであることです。それぞれの Counter オブジェクトを比較するか、両方の文字列をソートします。Counter の使用は O(n)、ソートは O(n log n) です。Counter を使う方法が最適で、定義をそのまま表現できます。
from collections import Counter
def isAnagram(s, t):
return Counter(s) == Counter(t)
# Alternative: manual frequency array for lowercase letters only
def isAnagram_arr(s, t):
if len(s) != len(t):
return False
freq = [0] * 26
for c in s: freq[ord(c) - ord('a')] += 1
for c in t: freq[ord(c) - ord('a')] -= 1
return all(f == 0 for f in freq)
print(isAnagram('anagram', 'nagaram')) # True
print(isAnagram('rat', 'car')) # False
print(isAnagram_arr('listen', 'silent')) # Trueアナグラムのグループ化（LeetCode 49）
LeetCode 49「アナグラムのグループ化」では、文字列のリストを受け取り、すべてのアナグラムを同じグループにまとめます。重要なポイントは、アナグラムではソート後の文字列が同じになることです。ソートした文字列のタプルをキーとする defaultdict(list) を使います（タプルはハッシュ化できます）。各グループは同じキーの下に蓄積されます。計算量は、L を文字列の最大長とすると O(n × L log L) です。
from collections import defaultdict
def groupAnagrams(strs):
groups = defaultdict(list)
for s in strs:
key = tuple(sorted(s)) # hashable canonical form
groups[key].append(s)
return list(groups.values())
print(groupAnagrams(['eat','tea','tan','ate','nat','bat']))
# [['eat','tea','ate'], ['tan','nat'], ['bat']]
# Alternative key: tuple of 26 character counts (O(L) not O(L log L))
def groupAnagrams_v2(strs):
groups = defaultdict(list)
for s in strs:
key = tuple(ord(c) - ord('a') for c in sorted(s))
groups[tuple(Counter(s)[chr(ord('a')+i)] for i in range(26))].append(s)
return list(groups.values())
頻度の高い上位 K 個の要素（LeetCode 347）
LeetCode 347「頻度の高い上位 K 個の要素」では、最も頻度の高い k 個の要素を返します。直接的な方法は O(n log n) です。頻度を数え、頻度の降順にソートして、先頭から k 個を取得します。最適な O(n) の方法では、バケットソートを使います。頻度（1 から n）をインデックスとするバケットを作り、各要素を頻度に対応するバケットに入れた後、頻度の高いバケットから順に走査して k 個の要素を集めます。
from collections import Counter
def topKFrequent(nums, k):
freq = Counter(nums)
# Bucket sort by frequency
buckets = [[] for _ in range(len(nums) + 1)]
for num, count in freq.items():
buckets[count].append(num)
result = []
for i in range(len(buckets) - 1, -1, -1):
result.extend(buckets[i])
if len(result) >= k:
return result[:k]
return result
print(topKFrequent([1,1,1,2,2,3], 2)) # [1, 2]
print(topKFrequent([1], 1)) # [1]頻度順に文字を並べ替える（LeetCode 451）
LeetCode 451「頻度順に文字を並べ替える」では、文字列内の文字が頻度の降順で現れるように並べ替えます。頻度を数え、文字を頻度の降順にソートして連結します。Python では most_common を使うのが最も簡潔な方法です。計算量は、頻度順に重複しない文字をソートするため O(n log n) です。
from collections import Counter
def frequencySort(s):
freq = Counter(s)
return ''.join(ch * count for ch, count in freq.most_common())
print(frequencySort('tree')) # 'eetr' or 'eert'
print(frequencySort('cccaaa')) # 'cccaaa' or 'aaaccc'
print(frequencySort('Aabb')) # 'bbAa' or 'bbaA'タスクスケジューラ（LeetCode 621）
LeetCode 621「タスクスケジューラ」では、タスクとクールダウン時間 n が与えられたとき、すべてのタスクを完了するための最小時間を求めます。重要なポイントは、最も頻度の高いタスクが全体の構成を決めることです。最も頻度の高いタスクを max_count 個配置し、その間に (n) 個の間隔を設けます。最小時間の合計は max((max_count - 1) * (n + 1) + num_tasks_with_max_count, total_tasks) です。間隔を埋めるのに十分な種類のタスクがある場合、アイドル時間は 0 になります。
from collections import Counter
def leastInterval(tasks, n):
freq = Counter(tasks)
max_count = max(freq.values())
# How many tasks share the max frequency
num_max = sum(1 for v in freq.values() if v == max_count)
# Minimum slots needed based on most frequent task
min_slots = (max_count - 1) * (n + 1) + num_max
return max(min_slots, len(tasks))
print(leastInterval(['A','A','A','B','B','B'], 2)) # 8
print(leastInterval(['A','A','A','B','B','B'], 0)) # 6
print(leastInterval(['A','A','A','A','B','B','B','C','C','D'], 2)) # 10Counter による過半数判定
LeetCode 169「多数決要素」では、n/2 回を超えて現れる要素を求めます。Boyer-Moore の多数決アルゴリズムは空間計算量 O(1) の最適な解法ですが、Counter.most_common(1) を使えば、O(n) 時間、O(n) 空間で直接解決できます。面接で O(1) 空間が求められている場合は、次の発展的な解法として Boyer-Moore を提示してください。追加の空間が許される場合は、Counter のほうが簡潔です。
from collections import Counter
def majorityElement_counter(nums):
freq = Counter(nums)
return freq.most_common(1)[0][0]
# Boyer-Moore O(1) space
def majorityElement_moore(nums):
candidate, count = None, 0
for num in nums:
if count == 0:
candidate = num
count += (1 if num == candidate else -1)
return candidate
nums = [2, 2, 1, 1, 2, 2, 2]
print(majorityElement_counter(nums)) # 2
print(majorityElement_moore(nums)) # 2最初の重複しない文字
LeetCode 387「文字列内で最初に一意となる文字」では、ちょうど1回だけ現れる最初の文字のインデックスを求めます。2回の走査で解決します。1回目の走査で頻度を数え、2回目の走査で個数が 1 の最初の文字を探します。計算量は O(n)、空間計算量は、アルファベットが 26 文字に固定されているため O(1) です。
from collections import Counter
def firstUniqChar(s):
freq = Counter(s)
for i, ch in enumerate(s):
if freq[ch] == 1:
return i
return -1
print(firstUniqChar('leetcode')) # 0 (l)
print(firstUniqChar('loveleetcode')) # 2 (v)
print(firstUniqChar('aabb')) # -1部分配列の合計が K（LeetCode 560）
LeetCode 560「部分配列の合計が K」では、合計が k になる部分配列の個数を数えます。総当たり法では O(n²) かかります。O(n) の方法では、現在までの累積和と、これまでに現れた累積和の頻度マップを保持します。各位置 i について、i で終わる合計 k の部分配列の個数は、それ以前の累積和のうち (current_prefix_sum - k) と等しいものの個数になります。インデックス 0 から始まる部分配列を扱うため、最初にマップを {0: 1} で初期化します。
from collections import defaultdict
def subarraySum(nums, k):
freq = defaultdict(int)
freq[0] = 1 # prefix sum of 0 seen once (empty prefix)
prefix_sum = 0
count = 0
for num in nums:
prefix_sum += num
# How many earlier prefix sums allow a k-sum subarray ending here
count += freq[prefix_sum - k]
freq[prefix_sum] += 1
return count
print(subarraySum([1, 1, 1], 2)) # 2
print(subarraySum([1, 2, 3], 3)) # 2
print(subarraySum([1, -1, 1, -1, 1], 0)) # 4Counter の算術演算と共通部分
Counter は算術演算をサポートします。+ はマージ（個数を加算）、- は減算（0 で打ち切り）、& は最小値（共通部分）、| は最大値（和集合）を取ります。これらの演算により、「複数の文字列に共通する文字を見つける」や「一方の文字列をもう一方のアナグラムにするために必要な最小限の文字削除」といった問題を簡潔に解けます。
from collections import Counter
A = Counter('abccdd')
B = Counter('ccdde')
print('Add: ', dict(A + B)) # sum of counts
print('Subtract: ', dict(A - B)) # A - B, clipped at 0
print('Intersect:', dict(A & B)) # min of shared counts
print('Union: ', dict(A | B)) # max counts
# Min steps to make s anagram of t (LeetCode 1347)
s, t = 'leetcode', 'practice'
diff = Counter(t) - Counter(s)
print('Chars to add:', sum(diff.values())) # 5まとめ：頻度カウントを使う場面
頻度カウントは、並べ替えれば同じになる2つの文字列（アナグラム）が等価かどうかの確認、最頻出または最も出現頻度の低い要素の検索、コレクションに必要な「材料」がそろっているかの検証、部分配列や部分文字列の問題を累積和とマップの問題に変換する場合に使います。重要なのは、グループ内の順序は関係なく、個数だけが重要だということです。
明確さを優先して、常に Counter を使ってください。より細かな制御が必要な場合や、アルファベットが限定されていて厳密に O(1) 空間にしたい場合に限り、通常の dict や配列に切り替えます。
理解度チェック
このレッスンで扱った Data Structures & Algorithms — Coding Interview Prep の概念について、理解度を確認しましょう。
レッスンのまとめ
このレッスンでは、Counter によって most_common、算術演算子、ゼロをデフォルトとするアクセスを利用した O(n) の頻度カウントができること、正規形（ソート済みタプル）によるグループ化によって、アナグラムのグループ化を O(nL log L) で解決できること、そして累積和と頻度マップによって、部分配列の合計が k になる問題を O(n²) から O(n) に変換できることを学びました。次は、最長連続系列の問題と LRU キャッシュの設計に取り組みます。
よくある質問
「頻度カウントとグループ化」レッスンは無料ですか？
はい。「頻度カウントとグループ化」の完全なテキストはこのウェブで無料で読めます。インタラクティブに演習し（組み込みコードエディタと24時間対応のAIチューター）、Coding Interview Prepコースの残りをアンロックするには、CoddyKit PROにアップグレードしてください。 Coding Interview Prepコースには全4レッスンが含まれています。
「頻度カウントとグループ化」で何を学びますか？
Counterとdefaultdictで文字頻度を数え、ソートしたキーでアナグラムをグループ化し、出現頻度上位k個の要素を見つけます。 ブラウザで直接実行するハンズオンコードでCoding Interview Prepを演習し、24時間対応のAIチューターがレッスンを進める中での質問に答えます。
Coding Interview Prepを始めるのに経験は必要ですか？
事前経験は必要ありません。CoddyKitのCoding Interview Prepは初級者から上級者向けに構成されているため、ここから始めるか最初から始めて、自分のペースで進むことができます。 これはレッスン3/4です。
「頻度カウントとグループ化」レッスンにはどのくらい時間がかかりますか？
ほとんどのCoddyKitレッスンは約5～10分かかります。各レッスンはコンパクトでインタラクティブなので、着実に進歩し、ウェブとアプリ全体で正確に前回の場所から再開できます。
このCoding Interview Prepレッスンでコードを書いて実行できますか？
はい。すべてのCoding Interview Prepレッスンに組み込みコードエディタが含まれているため、ブラウザでリアルコードを書いて実行し、即座のAIフィードバックを取得できます。ローカル設定は不要です。
このコースのすべてのレッスン
- ハッシュ関数の内部動作と衝突処理
- Two-Sumとその多様な派生問題
- 頻度カウントとグループ化
- 最長連続列とLRUキャッシュ