Sub-RBS (Hard Version)

The nasty-looking definition collapses to a much cleaner one:

$$\operatorname{score}(t)= \begin{cases} |t|-2, & t \text{ is regular and is a concatenation of at least two non-empty regular sequences},\\ 0, & \text{otherwise}. \end{cases}$$

That is the whole trick. The rest is just counting without doing exponential nonsense.

Call a non-empty regular bracket sequence primitive if its balance is positive at every proper prefix. For example, $\texttt{(())}$ is primitive, while $\texttt{()()}$ is not.

First, suppose $t$ is regular and non-primitive. Then

$$t = AB$$

where $A$ and $B$ are both non-empty regular sequences. Let $A$ start with $\texttt{(}$ and end with its matching closing bracket $\texttt{)}$. Delete exactly those two characters from $A$. The remaining sequence is still regular after being followed by $B$, because removing the outer pair of a primitive component keeps the inside regular.

What happens lexicographically? Before the boundary, the deleted opening bracket eventually causes a later character to shift left. Since $A$ returns to balance $0$ before $B$, the first actual improvement is that a $\texttt{(}$ from the next component can appear where $t$ had a $\texttt{)}$. So the new subsequence is better. Its length is $|t|-2$, which is the maximum possible positive score because a better subsequence cannot have length $|t|$.

Now suppose $t$ is primitive. Any proper regular subsequence $r$ must be shorter than $t$. For $r$ to be better, at the first difference it must put $\texttt{(}$ where $t$ has $\texttt{)}$. That means before this later $\texttt{(}$ moved left, the deleted prefix contained more closing brackets than opening brackets. But in a primitive regular sequence, every proper prefix has positive balance. You cannot delete a balanced number of total brackets and already have a prefix deletion with negative balance in the right way without breaking regularity. More concretely: the outer first $\texttt{(}$ and last $\texttt{)}$ wrap the whole sequence, and any regular subsequence remains trapped inside that outer structure, so it cannot become lexicographically larger than the original wrapper. Primitive sequences contribute $0$.

So we only need to sum $|t|-2$ over subsequences $t$ of $s$ that are regular and have already returned to balance $0$ before their final character.

We process $s$ left to right and build chosen subsequences. A state needs:

• current balance $b$,
• whether we have chosen anything yet,
• whether the chosen subsequence has already completed a non-empty regular block before the current end.

Let

$$dp[b][z]$$

store two values for partial subsequences:

• count of ways,
• total chosen length over those ways.

Here $z=1$ means the subsequence has had a proper return to balance $0$ after being non-empty. Once this happens, if the final balance later becomes $0$, the finished subsequence is non-primitive and contributes.

When reading a character, we can skip it or take it.

If we take $\texttt{(}$, balance increases by $1$.

If we take $\texttt{)}$, balance decreases by $1$, so this is only legal when $b>0$. After taking it, if the new balance is $0$ and the subsequence is not empty, we have just finished a regular block. This should set $z=1$ only if this return to $0$ is proper, meaning there will be more chosen characters later. Since we do not know the future, the easiest way is to set a flag whenever a partial subsequence has balance $0$ and positive length; later, if we extend it with another $\texttt{(}$, that old zero becomes a proper internal return.

A cleaner implementation uses states:

• $started$: handled implicitly by length/count,
• $good$: we have previously had balance $0$ and then extended afterward.

When adding a $\texttt{(}$ to a partial subsequence with balance $0$ and positive length, we set $good=1$, because we just started a second block. That exactly means the final sequence will be non-primitive if it eventually closes.

At the end, every state with balance $0$ and $good=1$ represents a regular non-primitive subsequence. Its contribution is

$$\sum (|t|-2)=\text{totalLength}-2\cdot\text{count}.$$

The empty subsequence never contributes; the DP naturally ignores it because it has length $0$ and never becomes good.

Complexity is tiny:

$$O(n^2)$$

per test case, with $O(n)$ states per flag. With $n\le 100$, this is comfortably inside the limit. No heroics, no black magic, just the right invariant.