Pythonで同じ文字が連続する最長部分文字列の長さを求めるプログラム

この記事では、Pythonを使って「同じ文字が連続している最長の部分文字列の長さ」を求める方法を解説します。

例えば、入力が "abbbaccabbbba" の場合、b が4つ連続して並んでいる箇所があるため、出力は 4 となります。

解法のアプローチ

この問題は、文字列を先頭から順番に走査し、隣接する2つの文字を比較することで解決できます。具体的な手順は以下のとおりです。

• 文字列 s の長さが 0 の場合は、そのまま 0 を返します。
• s の末尾に空白文字を1つ追加します。これは、ループ処理の際に文字列の最後にある連続グループも確実に確定させるためのテクニックです。
• カウンター ct と一時変数 tem をそれぞれ 1 で初期化します。
• i を 0 から s の長さ - 2 まで繰り返し処理を行います。
  • s[i] と s[i+1] が同じ文字の場合：tem を 1 増やします。
  • 異なる文字の場合：ct に tem と ct のうち大きい方を代入し、tem を 1 にリセットします。
• 最後に ct を返します。

実装例

class Solution:
   def solve(self, s):
       if len(s)==0:
           return 0
       s+=' '
       ct=1
       tem=1
       for i in range(len(s)-1):
           if s[i]==s[i+1]:
               tem+=1
           else:
               ct=max(tem,ct)
               tem=1
       return ct
ob = Solution()
print(ob.solve("abbbaccabbbba"))

入力

"abbbaccabbbba"

出力

4

コードのポイント

末尾への空白追加： 文字列の最後にダミー文字（空白）を追加することで、「現在の連続カウントを確定する」という処理を特別な条件分岐なしで実現できます。これにより、ループ内のコードがシンプルになり、バグも発生しにくくなります。

計算量： このアルゴリズムは文字列を1回だけ走査するため、時間計算量は O(n)、空間計算量は O(1) となり、非常に効率的です。長い文字列に対しても高速に動作します。