Sofia and Strings
Contest: Codeforces Round 910 (Div. 2)
Difficulty rating: 2200
Tags: data structures, greedy, sortings, strings, two pointers

Sofia has a string $$$s$$$ of length $$$n$$$, consisting only of lowercase English letters. She can perform operations of the following types with this string.

1. Select an index $$$1 \le i \le |s|$$$ and remove the character $$$s_i$$$ from the string.
2. Select a pair of indices $$$(l, r)$$$ ($$$1 \le l \le r \le |s|$$$) and sort the substring $$$s_{l} s_{l+1} \ldots s_r$$$ in alphabetical order.

Sofia wants to obtain the string $$$t$$$ of length $$$m$$$ after performing zero or more operations on string $$$s$$$ as described above. Please determine whether it is possible or not.

Input format:
The first line contains one integer $$$t$$$ ($$$1 \leq t \leq 10\,000$$$) — the number of test cases.

The first line of each test case contains two integers $$$n$$$, $$$m$$$ ($$$1\leq m \leq n \leq 2\cdot 10^5$$$) — the lengths of string $$$s$$$ and $$$t$$$, respectively.

The second line of each test case contains the string $$$s$$$ of length $$$n$$$, consisting only of lowercase English letters.

The third line of each test case contains the string $$$t$$$ of length $$$m$$$, consisting only of lowercase English letters.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2\cdot 10^5$$$.

Output format:
For each test case, output "YES" if Sofia can obtain the string $$$t$$$ from $$$s$$$ using the operations above. Otherwise, output "NO".

You can output the answer in any case (upper or lower). For example, the strings "yEs", "yes", "Yes", and "YES" will be recognized as positive responses.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
In the first test case, Sofia can perform the following operation:

1. operation of the second type with $$$l=1$$$ and $$$r=5$$$: string $$$s$$$ becomes $$$\mathtt{afios}$$$ after it.

In the second test case, Sofia can perform the following operations:

1. operation of the second type with $$$l=1$$$ and $$$r=2$$$: string $$$s$$$ becomes $$$\mathtt{bca}$$$ after it;
2. operation of the first type with $$$i=3$$$: string $$$s$$$ becomes $$$\mathtt{bc}$$$ after it.

In the third test case, it can be shown that it is impossible to obtain $$$t$$$ from $$$s$$$ using the provided operations.

Example input:
8
5 5
sofia
afios
3 2
cba
bc
5 1
sofia
e
15 7
anavolimilovana
aamanan
26 4
abcdefghijklmnopqrstuvwxyz
nope
26 4
zyxwvutsrqponmlkjihgfedcba
nope
7 3
apricot
cat
3 3
cba
acb

Example output:
YES
YES
NO
YES
NO
YES
NO
YES

Editorial:
Notice how sorting only the substrings of length $$$2$$$ is enough. Try a greedy approach.
We sort only the substrings of length $$$2$$$. We can swap two adjacent characters if the first is greater than or equal to the second. Let us fix some character $$$s_i$$$ and presume we want to change its position to $$$j$$$. We have to perform the described swaps if they are possible. More formally:
* if $$$j<i$$$, then every character in the segment $$$s_j s_{j+1} \ldots s_{i-1}$$$ must be greater than or equal to $$$s_i$$$; * if $$$i<j$$$, then every character in the segment $$$s_{i+1} s_{i+2} \ldots s_j$$$ must be smaller than or equal to $$$s_i$$$.
We want to reorder the string $$$s$$$ and get the string $$$s'$$$. Then, we check if we can delete some characters in $$$s'$$$ to achieve $$$t$$$. In other words, we want $$$t$$$ to be a subsequence of $$$s'$$$. A general algorithm that checks if the string $$$a$$$ is a subsequence of the string $$$b$$$ is as follows. We iterate through $$$a$$$, and for each character, we find its first next appearance in $$$b$$$. If such a character does not exist, we conclude that $$$a$$$ is not a subsequence of $$$b$$$. If we complete the iteration gracefully, then $$$a$$$ is a subsequence of $$$b$$$. We will try to check if $$$t$$$ is a subsequence of $$$s$$$, but we allow ourselves to modify $$$s$$$ along the way.
We maintain $$$26$$$ queues for positions of each lowercase English letter in the string $$$s$$$. We iterate through the string $$$t$$$, and for every character $$$t_i$$$, we try to move the first available equivalent character in $$$s$$$ to position $$$i$$$. In other words, at every moment, the prefix of string $$$s$$$ is equal to the prefix of string $$$t$$$ (if possible). For the current character $$$t_i$$$ and the corresponding $$$s_j$$$, prefixes $$$t_1t_2\dots t_{i-1}$$$ and $$$s_1s_2\dots s_{i-1}$$$ are the same, which means that $$$j\geq i$$$. To move $$$s_j$$$ to position $$$i$$$, we need to delete all characters between $$$s_i$$$ and $$$s_j$$$ that are smaller than $$$s_j$$$. We will delete them and all characters from the current prefix $$$s_1s_2\dots s_{i-1}$$$ from the queues because they are no longer candidates for $$$s_j$$$. By doing so, $$$s_j$$$ will be the first character in the corresponding queue. If at some moment in our greedy algorithm, the queue we are looking for becomes empty, then the answer is NO. Otherwise, we will make the prefix $$$s_1s_2\dots s_m$$$ equal to the $$$t$$$ and delete the remaining characters from $$$s$$$.
Why is this greedy approach optimal? Let's suppose for some character $$$t_{i_1}$$$ we chose $$$s_{j_1}$$$ and for $$$t_{i_2}$$$ we chose $$$s_{j_2}$$$, such that $$$i_1< i_2$$$, $$$j_1>j_2$$$ and $$$t_{i_1}=t_{i_2}=s_{j_1}=s_{j_2}$$$. We need to prove that if we can move $$$s_{j_1}$$$ to position $$$i_1$$$ and $$$t_{i_2}$$$ to position $$$i_2$$$, when we can move $$$s_{j_2}$$$ to $$$i_1$$$ and $$$s_{j_1}$$$ to $$$i_2$$$. In the moment when we chose $$$s_{j_1}$$$, prefixes $$$t_1t_2\dots t_{i_1-1}$$$ and $$$s_1s_2\dots s_{i_1-1}$$$ are the same, so $$$j_1\geq i_1$$$. Similarly, $$$j_2\geq i_2$$$, which means the only possibility is $$$i_1<i_2\leq j_2<j_1$$$.
If we can move $$$s_{j_1}$$$ to position $$$i_1$$$, than we can also move $$$s_{j_2}$$$ to $$$i_1$$$ because $$$s_{j_1}=s_{j_2}$$$ and $$$j_2<j_1$$$. Also, if we can move $$$s_{j_1}$$$ to $$$i_1$$$, than we can move $$$s_{j_1}$$$ to $$$i_2$$$ because $$$i_1<i_2$$$, from which it follows that we can move $$$s_{j_2}$$$ to $$$i_2$$$, because $$$s_{j_2}=s_{j_1}$$$ and $$$j_2<j_1$$$.
The overall complexity is $$$O(\alpha \cdot (n+m))$$$, where $$$\alpha$$$ is the alphabet size ($$$\alpha=26$$$ in this problem).