Pythonで文字列中の回文部分文字列の数を数える方法

問題の概要

ある文字列が与えられたとき、その文字列に含まれる回文（パリンドローム）部分文字列がいくつあるかを数える問題を考えてみましょう。

ここで重要なのは、開始インデックスまたは終了インデックスが異なる部分文字列は、たとえ同じ文字列で構成されていても別々の部分文字列として数えるという点です。

例えば、入力が "aaa" の場合、出力は 6 になります。これは「a」「a」「a」「aa」「aa」「aaa」という6つの回文部分文字列が存在するためです。

解決のアプローチ

この問題は、以下の手順に従って解くことができます。

1. カウンターを 0 で初期化します。
2. i を 0 から文字列の長さまで繰り返します。
   • j を i + 1 から文字列の長さ + 1 まで繰り返します。
     • インデックス i から j までの部分文字列を temp として取り出します。
     • temp が回文であれば、カウンターを 1 増やします。
3. 最後にカウンターの値を返します。

Pythonでの実装例

それでは、実際のコードを見て理解を深めましょう。

class Solution:
    def countSubstrings(self, s):
        counter = 0
        for i in range(len(s)):
            for j in range(i+1, len(s)+1):
                temp = s[i:j]
                if temp == temp[::-1]:
                    counter += 1
        return counter

ob1 = Solution()
print(ob1.countSubstrings("aaaa"))

入力

"aaaa"

出力

10

コードのポイント

• s[i:j] によって、開始位置 i から終了位置 j までのすべての部分文字列を効率的に取り出しています。
• temp[::-1] はスライス記法を使った文字列の反転です。元の文字列と反転した文字列が一致すれば、それは回文であると判定できます。
• 二重ループにより、すべての開始位置・終了位置の組み合わせを網羅的にチェックしているため、同じ文字でも位置が異なれば別々にカウントされます。

計算量について

この実装はシンプルで分かりやすい反面、計算量は O(n³) になります（部分文字列の組み合わせが O(n²)、各回文判定に O(n) かかるため）。文字列が長くなる場合は、中心拡張法（O(n²)）や Manacher のアルゴリズム（O(n)）などのより効率的な手法も検討するとよいでしょう。