Pythonで1種類の文字だけを含む部分文字列の総数を求めるプログラム

問題の概要

小文字の英字のみで構成される文字列 s が与えられたとき、「1種類の文字だけで構成されている部分文字列」の総数を求めます。

例えば、入力が "xxyy" の場合、出力は 6 になります。条件を満たす部分文字列は [x, x, xx, y, y, yy] の6つだからです。

解決のアプローチ

この問題は、連続して同じ文字が並ぶ区間（ラン）ごとに考えると効率的に解けます。長さ n の同一文字の連続区間から作れる部分文字列の数は n(n+1)/2 個ですが、ループ内で「現在の文字が何文字連続しているか」をカウントしながら合計へ加算していけば、結果的に同じ値が得られます。

具体的な手順は次のとおりです。

• 合計値 total を 0 で初期化する
• 前回の文字 previous を空文字列で初期化する
• 文字列 s の各文字 c について以下を繰り返す
  • c が previous と異なる場合：previous を c に更新し、連続カウント in_a_row を 1 にリセットする
  • c が previous と同じ場合：in_a_row を 1 増やす
  • いずれの場合も、in_a_row の値を total に加算する
• 最後に total を返す

実装例

class Solution:
    def solve(self, s):
        total = 0
        previous = ''
        for c in s:
            if c != previous:
                previous = c
                in_a_row = 1
            else:
                in_a_row += 1
            total += in_a_row
        return total

ob = Solution()
print(ob.solve("xxyy"))

入力

"xxyy"

出力

6

処理の流れを確認

入力 "xxyy" の場合、処理は次のように進みます。

• 1文字目 'x'：previous と異なるため in_a_row = 1、total = 1
• 2文字目 'x'：previous と同じため in_a_row = 2、total = 3
• 3文字目 'y'：previous と異なるため in_a_row = 1、total = 4
• 4文字目 'y'：previous と同じため in_a_row = 2、total = 6

最終的な total は 6 となります。"xx" の部分からは x・x・xx の3つ、"yy" の部分からは y・y・yy の3つが数えられ、合計6個の部分文字列が正しく検出されています。

計算量

文字列を一度走査するだけなので、時間計算量は O(n)、追加のメモリ使用量は O(1) で済みます。長い文字列に対しても高速に動作するのが特徴です。