Pythonで文字列の相異なる部分列の数を数えるプログラム

文字列 s が与えられたとき、その文字列から作ることができる相異なる部分列(サブシーケンス)の総数を求める問題です。答えが非常に大きくなる可能性があるため、結果は 10⁹ + 7 で割った余りとして返します。

たとえば、入力が s = "bab" の場合、出力は 6 になります。これは "a"、"b"、"ba"、"ab"、"bb"、"bab" の 6 つの異なる部分列が存在するためです。

解法のアプローチ

この問題は動的計画法(DP)を用いて効率的に解くことができます。手順は以下の通りです。

• dp := 文字列 s と同じ長さの配列を作成し、すべての要素を 0 で初期化する
• m := 10⁹ + 7(剰余を取るための定数)
• 文字列 s の各インデックス i と文字 char について、次の処理を行う
  • ind := インデックス i より前の範囲で、char と同じ文字が最後に現れた位置(rfind で検索)
  • ind が -1 の場合(同じ文字がまだ一度も現れていない場合):dp[i] := 1 + (dp[0]〜dp[i-1] の合計) mod m
    それ以外の場合:dp[i] := (dp[ind]〜dp[i-1] の合計) mod m
• 最後に、dp の全要素の合計を m で割った余りを返す

考え方のポイント

各位置 i における dp[i] は、「i 番目の文字で終わる新しく追加される部分列」の数を表しています。同じ文字がすでに出現している場合は、過去に数えた部分列との重複を避けるため、前回の出現位置以降の合計だけを加算するのがポイントです。これにより、全体の部分列の重複カウントを防ぎながら正確な数え上げが可能になります。

実装例

理解を深めるために、以下の Python 実装を見てみましょう。

def solve(s):
    dp, m = [0] * len(s), 10**9 + 7
    for i, char in enumerate(s):
        ind = s.rfind(char, 0, i)
        dp[i] = 1 + sum(dp[:i]) % m if ind == -1 else sum(dp[ind:i]) % m
    return sum(dp) % m

s = "baby"
s = "baby"

入力

"baby"

出力

6