C++で解く「異なる部分列 II」：動的計画法による効率的な数え上げアルゴリズム

問題概要

文字列 S が与えられたとき、S の「異なる部分列（distinct subsequences）」の総数を求めることを考えます。ここで部分列とは、元の文字列から一部の文字を選んで並び順を保ったまま取り出した文字列のことです。答えは非常に大きな値になる可能性があるため、10⁹ + 7 で割った余りを返します。

例として、入力が "bab" の場合を考えてみましょう。このとき出力は 6 になります。実際に存在する異なる部分列は次の 6 つです。

"a"、"b"、"ba"、"ab"、"bb"、"abb"

解法のアプローチ

この問題は動的計画法（DP）を使うことで、文字列の長さに対して線形時間で解くことができます。ポイントは、「各アルファベットの文字で終わる部分列の数」を個別に記録しておくことです。

補助関数の定義

まず、モジュロ演算を安全に行うための補助関数を 3 つ定義します。

• add(a, b)：((a mod MOD) + (b mod MOD)) mod MOD を返します。
• sub(a, b)：(((a mod MOD) − (b mod MOD)) + MOD) mod MOD を返します。減算結果が負になるのを防ぐため、MOD を加算しています。
• mul(a, b)：((a mod MOD) × (b mod MOD)) mod MOD を返します。

メイン処理の流れ

• n := 文字列 s の長さとします。
• サイズ 26 の配列 dp を定義します。dp[c] は「文字 c で終わる部分列の数」を表します。
• res := 0 で初期化します。これはこれまでに見つけた部分列の総数です。
• s の先頭に空白を連結し、インデックスを 1 から扱いやすくします。
• i = 1 から n まで以下を繰り返します。
  • x := s[i]（現在の文字）
  • added := sub(add(res, 1), dp[x − 'a'])（今回新しく追加できる部分列の数）
  • dp[x − 'a'] := add(dp[x − 'a'], added)
  • res := add(res, added)
• 最後に res を返します。

なぜこの方法が機能するのか

新しい文字 x を読み込んだ瞬間、作れる新しい部分列の候補は「それまでの全部分列の末尾に x を付けたもの」と「x 単独」の合計、すなわち res + 1 個あります。しかし、過去に同じ文字 x が出現していた場合、その時点で「x で終わる部分列」と重複が発生します。そこで dp[x − 'a'] を差し引くことで、重複を正確に排除しながら数え上げることができます。

計算量

時間計算量は O(n)、空間計算量は O(26)＝O(1) です。文字列の長さに対して線形時間で処理できるため、非常に効率的な解法といえます。

C++ 実装例

#include <bits/stdc++.h>
using namespace std;
typedef long long int lli;
const lli MOD = 1e9 + 7;
class Solution {
   public:
   lli add(lli a, lli b){
      return ( (a % MOD) + (b % MOD) ) % MOD;
   }
   lli sub(lli a, lli b){
      return ( ( (a % MOD) - (b % MOD) ) + MOD ) % MOD;
   }
   lli mul(lli a, lli b){
      return ( (a % MOD) * (b % MOD) ) % MOD;
   }
   int distinctSubseqII(string s) {
      int n = s.size();
      vector <lli> dp(26);
      int res = 0;
      s = " " + s;
      for(lli i = 1; i <= n; i++){
         char x = s[i];
         int added = sub(add(res, 1) , dp[x - 'a']);
         dp[x - 'a'] = add(dp[x - 'a'], added);
         res = add(res, added);
      }
      return res;
   }
};
main(){
   Solution ob;
   cout << (ob.distinctSubseqII("bab"));
}

入力例

"bab"

出力例

6