概要

\(N\) 個の文字列を先頭の文字ごとにグループ分けし、最も多くの文字列を含むグループのサイズを求める問題です。

考察

• 各文字列について注目すべきは先頭の1文字だけです。文字列の残りの部分はグループ分けに一切影響しません。
• 先頭の文字は英小文字なので、グループは最大でも \(26\) 個（a ～ z）しかありません。
• 同じ文字列が複数回現れても重複除去はせず、そのまま数えます。

具体例: 文字列が apple, ant, banana, avocado, berry の場合： - a で始まるグループ: apple, ant, avocado → 3個 - b で始まるグループ: banana, berry → 2個 - 最大は a グループの 3 が答えです。

この問題は素朴に各文字列の先頭文字を数え上げるだけで十分高速に解けるため、特別な工夫は不要です。

アルゴリズム

1. \(N\) 個の文字列を順に読み込む。
2. 各文字列の先頭文字 s[0] を取り出し、その文字の出現回数をカウントする。
3. すべての文字列を処理した後、カウントの最大値を出力する。

Pythonでは collections.Counter を使うと、キーごとの出現回数を簡潔に管理できます。

from collections import Counter

N = int(input())
c = Counter()
for _ in range(N):
    s = input()
    c[s[0]] += 1  # 先頭文字のカウントを1増やす
print(max(c.values()))  # カウントの最大値を出力

• c[s[0]] += 1 により、先頭文字ごとに何個の文字列があるかを記録します。
• 最後に max(c.values()) で、全グループの中で最大の文字列数を取得します。

計算量

• 時間計算量: \(O(N)\) — 各文字列について先頭文字の取得とカウント更新を \(O(1)\) で行い、最後に最大 \(26\) 個の値から最大値を求めるため。
• 空間計算量: \(O(1)\) — カウンターに格納されるキーは英小文字の最大 \(26\) 種類なので、定数サイズです。（入力の文字列自体の格納は不要）

実装のポイント

• Counter を使わず、サイズ \(26\) の配列（リスト）を用意して ord(s[0]) - ord('a') をインデックスにする方法でも同様に解けます。

• \(N \geq 1\) が保証されているので、max(c.values()) が空の集合に対して呼ばれる心配はありません。

  ソースコード

from collections import Counter

N = int(input())
c = Counter()
for _ in range(N):
    s = input()
    c[s[0]] += 1
print(max(c.values()))

この解説は claude4.6opus-thinking によって生成されました。