Let $$$f_{l, r}$$$ denote $$$0$$$ if we cannot reduce the subarray $$$a_l,\dots,a_r$$$ to a single element. Otherwise it will denote the value this subarray can be reduced to.

Claim: If the subarray can be reduced to a single element, the value is always same, regardless the order of operations.

$$$f_{l,r}$$$ can be calculated by the following recursive relation, \begin{equation} $f_{l,r} = \begin{cases} a_l &\text{if $$$l = r$$$} \newline \max_{i = l}^{r — 1} [f_{l,i} = f_{i+1,r}] (f_{l,i} + 1) &\text{otherwise} \end{cases} \end{equation} Note: $$$[a]$$$ evaluates to $$$0$$$ if a is false, and $$$1$$$ otherwise.$$$\newline$$$ The remaining problem is trivial.

Let $$$dp_i$$$ be the minimum length the prefix $$$a_1,a_2,\dots,a_i$$$ can be reduced to. We can formulate the simple recursive relation $$$dp_i = \min_{2 \leq j \leq i, \ f_{j,i} \ne 0} \ \ dp_{j-1} + f_{j,i}$$$ where $$$dp_1 = 1.$$$ $$$dp_n$$$ is our answer.

We can iterate over all prefixes of $$$t$$$ and try to create the prefix and the remaining suffix of $$$t$$$ as two disjoint subsequences from $$$s$$$. So the problem reduces to finding if two strings $$$a$$$ and $$$b$$$ can be disjoint subsequence of a given string $$$s$$$.

The reduced problem given as a hint can be trivially solved with dp using 3 states: let $$$f_{i,j,k}$$$ denote whether the prefix of $$$a$$$ of size $$$j$$$ and prefix of $$$b$$$ of size $$$k$$$ can be created by using the first $$$i$$$ characters of $$$s$$$ in a disjoint manner. $$$f_{i,j,k}$$$ can be easily calculated. If $$$s_i = a_j = b_k$$$ then we need to make a choice between inserting the current character in $$$a$$$ and $$$b$$$, we will explore both routes. Otherwise if $$$s_i$$$ matches with either one of the strings' current characters, we can use it in that string. \begin{equation} f_{i,j,k} = \begin{cases} 1 &\text{if } i = 0 \text{and } j = 0 \text{ and } k = 0\newline 0 &\text{if } i = 0 \text{ and (} j > 0 \text{ or } k > 0\text{)}\newline f_{i+1,j+1,k} \ | \ f_{i+1,j,k+1} &\text{if } s_i = a_j = b_k \newline f_{i+1,j+[s_i = a_j],k+[s_i=b_k]} &\text{otherwise} \end{cases} \end{equation} However this will run in $$$O(|s||a||b|)$$$ or $$$O(|s|^3)$$$ for every prefix, which will exceed limits in this problem. We will improve this by reducing a state and changing return parameters. Instead of iterating over the characters of $$$s$$$ and choosing between appending to $$$a$$$ or $$$b$$$, we ask — what is the smallest prefix of $$$s$$$ that can contain prefix of size $$$j$$$ of $$$a$$$ and size $$$k$$$ of $$$b$$$ as disjoint subsequences. Let's define the answer to $$$|s|+1$$$ if such a prefix doesn't exist, let this be denoted by $$$dp_{j,k}$$$. To calculate this, we can precompute $$$nxt_{i,c}$$$ which is the index of the next occurrence of character $$$c$$$ after the $$$i$$$-th index in $$$s$$$. Again defined to be $$$|s| + 1$$$ if it doesn't exist. \begin{equation} dp_{i,j} = \begin{cases} 0 &\text{if } i = j = 0\newline min\left(nxt_{dp_{i-1,\ j},\ a_i},\ \ nxt_{dp_{i,\ j-1},\ b_j}\right) &\text{otherwise} \end{cases} \end{equation} Which will run in $$$O(|s|^2)$$$ for every prefix.