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

問題の概要

ある文字列 s が与えられたとき、その中に含まれる「回文」となっている部分文字列の個数を求めることを考えます。

例えば、入力が s = "level" の場合、出力は 7 になります。これは、回文となっている部分文字列が ["l", "e", "v", "e", "l", "eve", "level"] の7つ存在するためです。

解き方：中心から左右へ拡張する手法

この問題は、各位置を回文の中心とみなし、左右の文字が一致する限り外側へ広げていく「中心拡張（Expand Around Center）」という手法で効率的に解くことができます。

check_palindrome() 関数の手順

1. 関数 check_palindrome() を定義します。引数として文字列、left、right を受け取ります。
2. ans を 0 で初期化します。
3. left >= 0 かつ right が s の長さ未満である間、以下を繰り返します。
   • s[left] と s[right] が一致する場合：ans を 1 増やし、left を 1 減らし、right を 1 増やします。
   • 一致しない場合：その時点の ans を返して終了します。
4. ループを抜けたら ans を返します。

メイン処理の手順

1. ans を 0 で初期化します。
2. char_index を 0 から s の長さまで順に処理します。
   • 奇数長の回文を数えるため、check_palindrome(s, char_index - 1, char_index + 1) の結果を加算します。
   • 偶数長の回文を数えるため、check_palindrome(s, char_index, char_index + 1) の結果を加算します。
3. 最後に ans + len(s) を返します。長さ1の文字はすべて回文になるため、その分をまとめて加算しています。

このアルゴリズムの計算量は O(n²) であり、動的計画法を使うよりもメモリ効率が良いのが特徴です。

それでは、以下の実装例を見て理解を深めましょう。

実装例

class Solution:
    def solve(self, s):
        def check_palindrome(string, left, right):
            ans = 0
            while left >= 0 and right < len(s):
                if s[left] == s[right]:
                    ans += 1
                    left -= 1
                    right += 1
                else:
                    return ans
            return ans
        ans = 0
        for char_index in range(len(s)):
            ans += check_palindrome(s, char_index - 1, char_index + 1)
            ans += check_palindrome(s, char_index, char_index + 1)
        return (ans) + len(s)
ob = Solution()
print(ob.solve("level"))

入力

"level"

出力

7

まとめ

このように、各文字を中心として左右に拡張しながら回文を判定することで、文字列内のすべての回文部分文字列を効率よく数えることができます。奇数長・偶数長の両方のパターンをカバーすることがポイントです。