Let \(S[0:i]\) denote the string consisting of the first \(i\) characters of the string \(S\). If \(i>|S|\), let it be a string whose prefix is \(S\) but which is different from any string whose prefix is \(S\).

Rephrasing the problem statement

We rephrase the problem statement as follows.

Question: we independently replace ? with a lowercase or uppercase English letter, chosen from the \(52\) options at random. What is the probability that \(S\) contains DDoS?

The answer is obtained as the answer to this question multiplied by \(52^q\).

Although this rephrasing is not mandatory, it is often a good idea to consider the probability instead of the numbers, or vice versa, for clear observations.

Example: ABC200 F, 第6回 ドワンゴからの挑戦状 予選 C (Only Japanese problem statement)

A simplified question

We first consider the following simplified version.

Question: find the probability that the string does not contain DDoS itself as a subsequence (not a DDoS-type string).

This problem can be solved with the following DP (Dynamic Programming):

\(DP[i][j]\) = the probability that the length-\(i\) string obtained by replacing ? in \(S[0:i]\) contains DDoS\([0:j]\), but not DDoS\([0:j+1]\), as a subsequence.

Original question

In the original problem, we can try a similar DP.

\(DP[i][j]\) = the probability that the length-\(i\) string obtained by replacing ? in \(S[0:i]\) contains the first \(j\) characters of a DDoS-type string, but does not contain the first \((j+1)\) characters of any DDoS-type string, as a subsequence

The transitions of this DP can be handled just as the simple version, except for \(j=1\) where an uppercase English character is appended to a string.

We now consider \(j=1\), where an uppercase English character is appended to a string. Here, the transition depend on whether the appended capital is already contained in the string, so the DP defined above cannot appropriately handle this.
At a glance, you may think that it requires to maintain which capitals are used in the string; but actually we can ignore the kinds and just memorize the number of distinct capitals.

We introduce the specific transition to show that memorizing the number of distinct capitals is enough. When a string \(T\) counted in \(DP[i][1]\) is succeeded by a capital \(c\), which of \(DP[i+1][*]\) should the resulting string \(T'\) be counted in?
Let \(x\) be the number of distinct capitals in \(S[0:i]\), and \(y\) be the number of distinct capitals in \(T\).
If \(S[0:i]\) contains \(c\), it transitions to \(DP[i+1][2]\).
Otherwise, \(T\) contains \(c\) if and only if \(c\) is one of the \((y-x)\) candidates. The probability of such an event is \(0\) if \(x=26\) and \(\frac{y-x}{26-x}\) otherwise.
Thus, our claim is justified.

Summary

We can solve the original problem with a DP with the following \(29\) states.

\(DP[i][state]\) = The number of length-\(i\) strings resulting from replacing the first ? in \(S[0:i]\) which (or the probability that that operation results in a string which):

• does not contain a capital;
• contains exactly \(y\) kinds of capitals, each occurring exactly once \((y=1,2,\ldots,26)\);
• contains a capital occurring multiple times, after which no lowercase letter occurs;
• contains a capital occurring multiple times, followed by a lowercase letter, after which no uppercase letter occurs.

Writer’s solution (C++)