Given a string S, count the subsequences equal to atcoder. A subsequence is formed by deleting zero or more characters without changing the order of the remaining characters. Different choices of positions count as different subsequences.
Let dp[j] be the number of ways to form the first j characters of atcoder from the characters processed so far. Initially, dp[0] = 1 represents the one way to form the empty prefix, and all other entries are zero. For each input character, visit matching target positions from right to left and add dp[j] into dp[j + 1], modulo 1,000,000,007. The descending order ensures that a character from the current input position cannot be used more than once: the source count still describes subsequences formed before this character was processed.
The invariant is that after processing any prefix of S, dp[j] counts exactly the index choices forming the first j target characters within that prefix. The answer is dp[7]. Each input character checks the seven target positions, so the time complexity is O(7N) and the auxiliary space is O(1).
Java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
import java.io.BufferedInputStream;
import java.io.IOException;
public class Main {
private static final long MOD = 1_000_000_007L;
private static final String TARGET = "atcoder";
public static void main(String[] args) throws IOException {
BufferedInputStream in = new BufferedInputStream(System.in);
int n = 0;
int c;
while ((c = in.read()) <= ' ') {
if (c == -1) return;
}
do {
n = n * 10 + c - '0';
c = in.read();
} while (c > ' ');
char[] s = new char[n];
int length = 0;
while (length < n) {
c = in.read();
if (c > ' ') s[length++] = (char) c;
}
long[] dp = new long[TARGET.length() + 1];
dp[0] = 1;
for (char ch : s) {
for (int j = TARGET.length() - 1; j >= 0; j--) {
if (ch == TARGET.charAt(j)) {
dp[j + 1] = (dp[j + 1] + dp[j]) % MOD;
}
}
}
System.out.println(dp[TARGET.length()]);
}
}