概要

\(N\) 個の文字列を「先頭の文字」が同じもの同士でグループ分けし、最も多くの文字列が含まれるグループの件数を求める問題です。

考察

この問題で重要なのは、「各文字列の 2 文字目以降は無視してよい」 という点と、「グループの候補は英小文字の ‘a’ から ‘z’ までの 26 種類しかない」 という点です。

例えば、入力が apple, ant, banana の場合： - ‘a’ で始まるグループ： apple, ant （2個） - ‘b’ で始まるグループ： banana （1個） となり、最大値は 2 です。

同じ文字列が複数回現れる場合もそれぞれ 1 個として数えるため、単純に各文字列の先頭 1 文字だけを確認し、その出現回数をカウントすればよいことになります。

アルゴリズム

1. 英小文字は 26 種類あるため、各文字の出現回数を記録するための長さ 26 の配列（または連想配列/辞書）を用意します。
2. 与えられた \(N\) 個の文字列 \(S_i\) について、以下の操作を繰り返します。
   • \(S_i\) の 1 文字目を取り出す。
   • その文字に対応する配列のカウントを 1 増やす。
3. 配列の中の最大値を出力します。

文字から配列のインデックス（0〜25）に変換するには、多くのプログラミング言語で用意されている ord 関数（文字の文字コードを返す関数）を利用すると便利です。ord(先頭文字) - ord('a') と計算することで、’a’ なら 0、’b’ なら 1、…、’z’ なら 25 という数値を得ることができます。

計算量

• 時間計算量: \(O(N)\)
  • \(N\) 個の文字列を 1 回ずつ走査するため、文字列の数 \(N\) に比例した時間で処理が終わります。
• 空間計算量: \(O(N + |\Sigma|)\)
  • 入力文字列の保存に \(O(N \times (\text{文字列の長さ}))\)、出現回数のカウント用に文字の種類数 \(|\Sigma| = 26\) の配列が必要です。

実装のポイント

• 高速な入出力: \(N\) が最大 \(10^5\) と比較的大きいため、Python の場合は sys.stdin.read().split() などを使って一括で入力を読み込むと実行時間を短縮できます。

• インデックスの計算: ord(first_char) - ord('a') を使うことで、アルファベットを直接配列の添字として扱うことができます。

• 重複の扱い: 問題文に「重複除去をせずに数える」とあるため、set などを使ってユニークな文字列にする必要はありません。単純にすべてカウントします。

  ソースコード

import sys

def solve():
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    n = int(input_data[0])
    strings = input_data[1:]
    
    counts = [0] * 26
    offset = ord('a')
    
    for i in range(n):
        first_char = strings[i][0]
        counts[ord(first_char) - offset] += 1
        
    print(max(counts))

if __name__ == "__main__":
    solve()

この解説は gemini-3-flash-thinking によって生成されました。