Pythonで先頭文字が同じ単語が連続する最長サブリストの長さを求める方法

問題の概要

小文字のアルファベットで構成された文字列のリスト words が与えられたとします。この中から「隣り合う単語の先頭文字がすべて同じである」最も長い連続するサブリスト(部分リスト)を見つけ、その長さを求めるのが今回の課題です。

たとえば、入力が ["she", "sells", "seashells", "on", "the", "sea", "shore"] の場合、出力は 3 になります。最も長い連続サブリストは ["she", "sells", "seashells"] であり、これらの単語の先頭文字はすべて 's' で共通しているためです。

解決のアプローチ

この問題は、リストを一度だけ走査しながら「現在の連続カウント」と「最大カウント」を更新していくシンプルな手法で解けます。手順は以下の通りです。

• カウンタ cnt を 1、最大値 maxcnt を 0、前回の先頭文字 prev_char を空文字列で初期化します。
• リスト内の各単語について、次の処理を繰り返します。
  • prev_char が空であれば、その単語の先頭文字を prev_char に設定します。
  • prev_char が単語の先頭文字と同じであれば、cnt を 1 増やします。
  • それ以外の場合は、prev_char を新しい先頭文字に更新し、cnt を 1 にリセットします。
• 毎回、maxcnt を maxcnt と cnt の大きい方の値で更新します。
• ループ終了後、maxcnt を返します。

Pythonでの実装例

理解を深めるために、実際のコードを見てみましょう。

def solve(words):
    cnt = 1
    maxcnt = 0
    prev_char = ""
    for word in words:
        if prev_char == "":
            prev_char = word[0]
        elif prev_char == word[0]:
            cnt += 1
        else:
            prev_char = word[0]
            cnt = 1
        maxcnt = max(maxcnt, cnt)
    return maxcnt

words = ["she", "sells", "seashells", "on", "the", "sea", "shore"]
print(solve(words))

入力

["she", "sells", "seashells", "on", "the", "sea", "shore"]

出力

3

処理の流れをトレースしてみる

入力例に対する各ステップの動きは次のようになります。

• "she" → prev_char が空のため 's' を設定(cnt=1)
• "sells" → 先頭文字が 's' で一致し、cnt=2
• "seashells" → 同様に一致し、cnt=3(maxcnt=3 に更新)
• "on" → 先頭文字が 'o' に変わり、cnt=1 にリセット
• "the" → 先頭文字が 't' に変わり、cnt=1
• "sea" → 先頭文字が 's' に変わり、cnt=1
• "shore" → 先頭文字が 's' で一致し、cnt=2

最終的に記録された最大値 3 が返されます。

計算量

このアルゴリズムはリストを一度だけ走査するため、時間計算量は O(n)(n は単語の数)、追加で必要なメモリは O(1) です。大規模なデータに対しても効率的に動作する、非常にシンプルかつ実用的なアプローチと言えます。