Pythonで文字列内の「大きなグループ」の位置を検出するアルゴリズム

小文字の英字のみで構成される文字列 S を考えます。このような文字列では、同じ文字が連続して現れる部分が「グループ」を形成します。たとえば、S = "abbxxxxzyy" の場合、グループは "a"、"bb"、"xxxx"、"z"、"yy" の5つに分けられます。このうち、3文字以上で構成されるグループを「大きなグループ(large group)」と定義します。

本記事では、文字列中に存在するすべての大きなグループについて、その開始位置と終了位置を求めるアルゴリズムを解説します。

たとえば、入力が "abcdddeeeeaabbbcd" の場合、出力は [[3,5],[6,9],[12,14]] となります。これは、インデックス3〜5の "ddd"、インデックス6〜9の "eeee"、インデックス12〜14の "bbb" がそれぞれ3文字以上の連続グループであることを示しています。

解法のアプローチ

この問題は、Python標準ライブラリの itertools.groupby を活用することで、簡潔かつ効率的に解くことができます。手順は以下の通りです。

• 結果を格納するための空のリスト ans を用意します。
• ここまで処理した文字数を追跡するカウンター csum を 0 で初期化します。
• groupby を使って、連続する同一文字ごとに文字列をグループ化します。
• 各グループについて、サイズが3以上であれば、開始位置 csum と終了位置 csum + グループサイズ - 1 のペアを ans に追加します。
• csum にグループのサイズを加算し、次のグループへ進みます。
• すべてのグループを処理したら、ans を返します。

実装例

以下が実際のPythonコードです。

from itertools import groupby

class Solution:
    def largeGroupPositions(self, S):
        ans = []
        csum = 0
        for a, b in groupby(S):
            grp = list(b)
            if len(grp) >= 3:
                ans.append([csum, csum + len(grp) - 1])
            csum += len(grp)
        return ans

ob = Solution()
print(ob.largeGroupPositions("abcdddeeeeaabbbcd"))

入力と出力

入力

"abcdddeeeeaabbbcd"

出力

[[3, 5], [6, 9], [12, 14]]

コードのポイント

itertools.groupby は、隣接する同一要素をまとめてイテレートできる便利な関数です。各グループのキー(文字)とグループ本体を受け取り、list(b) でグループをリスト化することで長さを取得できます。

計算量は文字列の長さを n とすると O(n) となり、各文字を一度だけ走査すればよいため、非常に効率的です。また、累積カウンター csum を使うことで、各グループの開始インデックスを毎回計算し直す必要がない点もポイントです。