Copy String

The operation is easier if you stop thinking about “changing letters” and start thinking about where each final letter came from.

In one operation, position $i$ can either keep its old character or copy the old character from $i-1$. So a character can spread one position to the right per operation. It can never move left. Also, $s_1$ is nailed to the floor forever.

After several operations, every position in the current string contains some original character from $s$.

Key Model

Suppose after $k$ operations, final position $i$ came from original position $p_i$.

Then we must have:

• $p_i \le i$, because characters only move right.
• $i-p_i \le k$, because a character moves at most one step per operation.
• $s_{p_i}=t_i$, because the copied character must match the target.
• The sequence $p_1,p_2,\dots,p_n$ is nondecreasing.

That last condition is the sneaky one. Why? Because copy paths cannot cross. A character used for a position on the left cannot originate to the right of a character used for a later position. The operation only allows “same position” or “one step from the left”, so origins stay ordered forever.

So the problem becomes:

Find the minimum $k$ such that for every target position $i$, we can choose a source position $p_i$ satisfying

$$\max(1,i-k) \le p_i \le i,$$ $$s_{p_i}=t_i,$$

and

$$p_1 \le p_2 \le \cdots \le p_n.$$

If no such choice exists for $k \le k_{\max}$, print -1.

Checking a Fixed $k$

For a fixed $k$, greedily scan target positions from left to right.

Maintain last, the source index chosen for the previous target position. For position $i$, we need the smallest source index $j$ such that:

• $j \ge last$,
• $j \ge i-k$,
• $j \le i$,
• $s_j=t_i$.

Choosing the leftmost valid $j$ is always best. It leaves as much room as possible for future positions. If even the leftmost valid choice does not exist, then no clever nonsense later can save us.

To implement this quickly, store the sorted positions of every letter in $s$. For each $t_i$, binary search in that letter's position list for the first position at least $\max(last,i-k)$. It must also be at most $i$.

This check is $O(n\log n)$.

Finding the Minimum

If a transformation is possible in $k$ operations, it is also possible in any larger number of operations. More time never hurts.

So binary search the smallest valid $k$ in $[0,k_{\max}]$.

If even $k_{\max}$ is invalid, output -1.

Constructing the Actual Strings

Once we know the minimum $k$, run the greedy check one more time and store the chosen source index $p_i$ for each final position.

Now we need to print the string after every operation, not just say “trust me bro”.

For target position $i$, its final character starts at position $p_i$ and needs $d_i=i-p_i$ steps to reach $i$.

At operation $r$:

• if $d_i \le r$, position $i$ should already be equal to $t_i$;
• otherwise, the character is still traveling, and position $i$ contains the original character from source $i-r$.

So the string after operation $r$ is:

$$ans_r[i] = \begin{cases} t_i, & i-p_i \le r,\\ s_{i-r}, & i-p_i > r. \end{cases}$$

using 0-based indices in code with the same idea.

Why does this sequence obey the operation? For each position, once the target copy wave reaches it, it keeps that final character. Before that, it is just the original character shifted right by $r$ positions. Each step either keeps the current value or copies from the left, exactly as required.

The total printed output size is $O(nk)$, and the statement guarantees the sum of $n\cdot k_{\max}$ is at most $10^6$, so this is totally fine.