Albocede DNA

This is a hard DP problem. The key is to find the iteration formular. Let's first consider a simpler problem in which we only need to guarantee that the subsequence is in a form of aaabbbcccddd. In other words, each letter appears more than once and they are in a order of abcd.

As for the simpler problem. We use $DP[i][j]$ denotes the count of subsequence in string str[0..i] that ends in letter j. So we have:

1. if str[i] == 'a', $DP[i][0] = DP[i - 1][0]\times 2 + 1.$
2. if str[i] == 'b', $DP[i][1] = DP[i - 1][1]\times 2 + DP[i - 1][0].$
3. if str[i] == 'c', $DP[i][2] = DP[i - 1][2]\times 2 + DP[i - 1][1].$
4. if str[i] == 'd', $DP[i][3] = DP[i - 1][3]\times 2 + DP[i - 1][2].$

The result is $DP[n][3]$.

As for our original problem. We have to seperate the cases of $DP[i][j]$ to several cases to enable controlling of letter count. Let $DP[i][j][k][c]$ means the count of valid subsequence ends with letter $c$ and the number of as minus number of cs is $j$ and the number of bs minus the number of ds is $k$. As all as is in front of cs and all bs is in front of ds, there is no point to record the cases that j < 0 and k < 0 as we won't start from those states to produce a valid subsequence.

After reduced the space uses, we can get a solution like:

import java.io.*;
import java.util.*;

public class AlbocedeDNA {
    static private int MOD = 1000000007;
    static private int[][][] dp = new int[512][512][4];
    private static int solve(String s) {
        for (int i = 0; i < 512; i++) {
            for (int j = 0; j < 512; j++) {
                for (int k = 0; k < 4; k++) {
                    dp[i][j][k] = 0;
                }
            }
        }
        char[] str = s.toCharArray();
        int n = str.length;
        for (int i = 1; i <= n; i++) {
            char c = str[i - 1];
            if (c == 'a') {
                for (int j = i; j >= 0; j--) {
                    dp[j + 1][0][0] = (dp[j + 1][0][0] + dp[j][0][0]) % MOD;
                }
                dp[1][0][0] = (dp[1][0][0] + 1) % MOD;
                dp[1][0][0] = (dp[1][0][0] + dp[0][0][3]) % MOD;
            } else if (c == 'b') {
                for (int j = 0; j < i; j++) {
                    for (int k = i; k >= 0; k--) {
                        dp[j][k + 1][1] = (dp[j][k + 1][1] + dp[j][k][1]) % MOD;
                    }
                    dp[j][1][1] = (dp[j][1][1] + dp[j][0][0]) % MOD;
                }

            } else if (c == 'c') {
                for (int k = 0; k < i; k++) {
                    for (int j = 0; j < i; j++) {
                        dp[j][k][2] = (dp[j][k][2] + dp[j + 1][k][2]) % MOD;
                        dp[j][k][2] = (dp[j][k][2] + dp[j + 1][k][1]) % MOD;
                    }
                }
            } else {
                for (int j = 0; j < i; j++) {
                    for (int k = 0; k < i; k++) {
                        dp[j][k][3] = (dp[j][k][3] + dp[j][k + 1][3]) % MOD;
                        dp[j][k][3] = (dp[j][k][3] + dp[j][k + 1][2]) % MOD;
                    }
                }
            }
        }
        return dp[0][0][3];
    }
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int N = in.nextInt();
        for (int t = 0; t < N; t++) {
            System.out.printf("Case #%d: %d\n", t + 1, solve(in.next()));
        }
    }
}