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.

Similar to the previous problem, this can be done in a straightforward manner. For every character of $$$s$$$, we can either choose to or delete it, or keep it in $$$s$$$ and try to make a substring equal to $$$p$$$ with it, while ensuring exactly $$$x$$$ characters are deleted in the end. But if we try to keep track of how much of $$$p$$$ has been built, how many characters have been deleted as well as which is the current character of $$$s$$$, there will be too many states and will exceed time limits. Here we can observe that we don't need to keep track of how much of $$$p$$$ has been currently built, because whenever we start building $$$p$$$ as a substring, it is always as good or better to finish it instead of leaving it incomplete(this is a consequence of substrings not overlapping). For every index, we can pre-calculate if a substring of $$$s$$$ equal to $$$p$$$ starts in this index in O(|s| * |p|) by brute-force, or O(|s| + |p|) using KMP or other matching algorithms. Now we only need to keep the current index and number of characters yet to be deleted as parameters, and for every index, we can delete it or try to complete a substring equal to $$$p$$$ starting from it. This can be calculated in $$$O(|s| * |s|)$$$ for all values of $$$x$$$.