問題

https://leetcode.com/problems/distinct-subsequences-ii/

文字列 $S$ の部分文字列の個数を $mod(10^9+7)$ で求めよ

考え方

部分文字列DPのverify問題。公式のeditorialでは文字列の重複を許して部分文字列を生成した後、重複分の文字列数を差し引く...という解法になっている。ここではけんちょんさんの記事に従って、部分文字列を作るときに常に辞書順最小が保たれるような遷移をして、重複がないように部分文字列を生成する解法で考える。

重要なのは「同じ部分文字列を得るとしたら、辞書順最小になるように遷移する」ということである。

例として abab について考えてみる。空文字を含めて、12個の部分文字列が生成できる。DP遷移は以下の図のように遷移する(はず...)。 " は空文字とする。

f:id:d_tutuz:20190202222304p:plain — DP遷移図

DPとして個数を数え上げる場合は、部分文字列の情報は不要で単に文字列の数でまとめて足していけばよいことになる。さて、上記のように辞書順最小を保ちながら遷移するためには、今いる位置 $i$ から次の a ~ z が出てくる最小の位置の情報が必要である。これは文字列を後ろから走査することで $O(N)$ で求めることができる。

DP遷移は配るDPで考えることができて、文字列 $S$ の $i$ 文字目以降で最初に文字 $c$ が現れる位置を $next[i][c]$ とすると

$dp[next[i][c]+1] += dp[i]$

となる。DP初期値は空文字を考慮して $dp[0] = 1$ となる。

       public int distinctSubseqII(String S) {

            int MOD = 1_000_000_007;
            int n = S.length();

            int[][] next = new int[n+1][26];
            fill(next, -1);
            for (int i = n-1; i >= 0; i--) {
                for (int j = 0; j < 26; j++) {
                    next[i][j] = next[i+1][j];
                    next[i][S.charAt(i)-'a'] = i;
                }
            }

            int[] dp = new int[n+1];
            dp[0] = 1;
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < 26; j++) {
                    if (next[i][j] < 0) continue;
                    dp[next[i][j] + 1] += dp[i];
                    dp[next[i][j] + 1] %= MOD;
                }
            }

            int ret = 0;
            for (int i = 0; i <= n; i++) {
                ret += dp[i];
                ret %= MOD;
            }

            ret = ret - 1 + MOD;
            return ret % MOD;

        }

        void fill(int[][] a, int v) {
            for (int i = 0; i < a.length; i++) {
                for (int j = 0; j < a[0].length; j++) {
                    a[i][j] = v;
                }
            }
        }