Strong Password
Contest: Educational Codeforces Round 151 (Rated for Div. 2)
Difficulty rating: 1400
Tags: binary search, dp, greedy, strings

Monocarp finally got the courage to register on ForceCoders. He came up with a handle but is still thinking about the password.

He wants his password to be as strong as possible, so he came up with the following criteria:

- the length of the password should be exactly $$$m$$$;
- the password should only consist of digits from $$$0$$$ to $$$9$$$;
- the password should not appear in the password database (given as a string $$$s$$$) as a subsequence (not necessarily contiguous).

Monocarp also came up with two strings of length $$$m$$$: $$$l$$$ and $$$r$$$, both consisting only of digits from $$$0$$$ to $$$9$$$. He wants the $$$i$$$-th digit of his password to be between $$$l_i$$$ and $$$r_i$$$, inclusive.

Does there exist a password that fits all criteria?

Input format:
The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of testcases.

The first line of each testcase contains a string $$$s$$$ ($$$1 \le |s| \le 3 \cdot 10^5$$$), consisting only of digits from $$$0$$$ to $$$9$$$ — the password database.

The second line contains a single integer $$$m$$$ ($$$1 \le m \le 10$$$) — the required length of the password.

The third line contains a string $$$l$$$ ($$$|l| = m$$$), consisting only of digits from $$$0$$$ to $$$9$$$ — the lower restriction on each digit.

The fourth line contains a string $$$r$$$ ($$$|r| = m$$$), consisting only of digits from $$$0$$$ to $$$9$$$ — the upper restriction on each digit. $$$l_i \le r_i$$$ for all $$$i$$$ from $$$1$$$ to $$$m$$$.

The sum of lengths of $$$s$$$ over all testcases doesn't exceed $$$3 \cdot 10^5$$$.

Output format:
For each testcase, print "YES" if there exists a password that fits all criteria. Print "NO" otherwise.

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

Note:
In the first testcase, Monocarp can choose password "50". It doesn't appear in $$$s$$$ as a subsequence.

In the second testcase, all combinations of three digits, each of them being from $$$1$$$ to $$$4$$$, fit the criteria on $$$l$$$ and $$$r$$$. However, all of them appear in $$$s$$$ as subsequences. For example, "314" appears at positions $$$[3, 5, 12]$$$ and "222" appears at positions $$$[2, 6, 10]$$$.

In the third testcase, Monocarp can choose password "4321". Actually, that is the only password that fits the criteria on $$$l$$$ and $$$r$$$. Luckily, it doesn't appear in $$$s$$$ as a subsequence.

In the fourth testcase, only "49" and "59" fit the criteria on $$$l$$$ and $$$r$$$. Both of them appear in $$$s$$$ as subsequences.

In the fifth testcase, Monocarp can choose password "11".

Example input:
5
88005553535123456
2
50
56
123412341234
3
111
444
1234
4
4321
4321
459
2
49
59
00010
2
10
11

Example output:
YES
NO
YES
NO
YES

Editorial:
Consider the naive solution. You iterate over all password options that fit the criteria on $$$l$$$ and $$$r$$$ and check if they appear in $$$s$$$ as a subsequence.
That check can be performed greedily: find the first occurrence of the first digit of the password, then find the first occurrence after it of the second digit of the password, and so on. If all digits are found, then it's present. Otherwise, it isn't.
Notice how the checks from the $$$i$$$-th digit onwards only depend on the position of the $$$(i-1)$$$-st digit. Moreover, to have a lower probability to find these digits, we want the $$$(i-1)$$$-st digit to be as much to the right as possible.
That leads us to the greedy solution to the full problem. Iterate over the first digit and choose the one that appears as much to the right as possible. Then the same for the second digit, and so on. If any digit is not found in the string after the starting position of the check, then the password that starts with the chosen digits is strong.
So far, the solution sounds like $$$O(nmD)$$$, where $$$D$$$ is the number of digits (equal to $$$10$$$). Which is actually fine under these constraints, but we can do better.
One option is to precalculate something to help us find the next occurrence of each digit. For example, that can be an array of positions of each digit. Then we can use lower_bound on it to find the next one. That would be $$$O(n + D + mD \log n)$$$.
Alternatively, you can calculate an array $$$\mathit{next}[i][j]$$$ that stores the next occurrence of digit $$$j$$$ from position $$$i$$$. It's possible to calculate $$$\mathit{next}[i]$$$ from $$$\mathit{next}[i + 1]$$$. Notice that only $$$\mathit{next}[i][s[i]]$$$ changes. So you can copy $$$\mathit{next}[i + 1]$$$ into $$$\mathit{next}[i]$$$ and set $$$\mathit{next}[i][s[i]] = i$$$. Now you can just query the array by looking into the corresponding cells. That would be $$$O(nD + mD)$$$.
Finally, let's analyze the complexity of the linear search better. So, for each digit, actually run a while loop that searches the string until it encounters that letter. We proposed that it is $$$O(nmD)$$$. Notice that if some iteration of the loop for the $$$i$$$-th digit passes a position $$$x$$$, then the digits from the $$$(i+1)$$$-st onwards won't look into it. So, such position can only be checked in $$$O(D)$$$ loops (all loops for the current digit). Thus, each of $$$n$$$ positions can only be accessed $$$O(D)$$$ times, making the solution $$$O(m + nD)$$$, which makes it the fastest of all our options. That is basically the same analysis as two pointers. $$$O(m)$$$ comes from the outer loop over digits that you can't really get rid of. However, you can say that $$$m \le n$$$ ($$$m > n$$$ can be solved in $$$O(1)$$$), and call the solution $$$O(nD)$$$.
Overall complexity: $$$O(m + nD)$$$ for each testcase.