Pythonで文字列の「良い分割」の数を求めるプログラム

ある文字列 s が与えられているとします。s を2つの空でない文字列 p と q に分割し、その連結が元の s と一致し、さらに p と q のそれぞれに含まれる異なる文字の種類数が等しいとき、この分割を「良い分割（good split）」と呼びます。この記事では、s に対して作れる良い分割の数を求める方法を解説します。

問題の例

たとえば、入力が s = "xxzxyx" の場合、出力は 2 になります。分割の仕方は複数ありますが、("xxz", "xyx") や ("xxzx", "yx") のように分割したときだけ、両側の異なる文字数が一致するため「良い分割」となります。

解決のアプローチ

この問題は、文字列を左から順に走査しながら、左右それぞれの異なる文字数を管理することで効率的に解けます。具体的な手順は以下の通りです。

• result を 0 で初期化します。
• left：左側の文字の出現頻度を記録するための空のマップ（Counter）を用意します。
• right：s に含まれる全文字の出現頻度をあらかじめカウントしておきます。
• s 内の各文字 c について次を繰り返します。
  • left[c] を +1 し、right[c] を −1 します。
  • right[c] が 0 になった場合は、キーごと削除して文字種としてカウントされないようにします。
  • left と right のサイズ（異なる文字の種類数）が一致していれば、result を +1 します。
• 最後に result を返します。

Pythonでの実装例

以下のコードでは、標準ライブラリの collections.Counter を使うことで、出現頻度の管理を簡潔に記述できます。

from collections import Counter
def solve(s):
    result = 0
    left, right = Counter(), Counter(s)
    for c in s:
        left[c] += 1
        right[c] -= 1
        if not right[c]:
            del right[c]
        if len(left) == len(right):
            result += 1
    return result

s = "xxzxyx"
print(solve(s))

入力

"xxzxyx"

出力

2

計算量について

このアルゴリズムは文字列を一度だけ走査すればよいため、時間計算量は O(n)、各Counterが保持するキー数は高々アルファベット種類数なので空間計算量も O(1)（文字種に依存）と非常に効率的です。単純にすべての分割位置を試して毎回文字種を数え直す O(n²) の方法と比べ、長い文字列でも高速に動作します。