Google OA 2024 - String Machine

You are given a string S1 of length N.

You have a machine that will generate a string Q of length M using a string S2 of length M.

However, the machine will not generate the string Q at once. Initially. you're given a string Q filled with the character " * ". The machine will add the characters of string S2 at specific positions one by one in string Q each second. You also have a permutation P of length M.

At the ith second of time, the machine will add P[i]th character of S2 to P[i]th position of Q. So, eventually at the end of Mth second, the whole string S2 will be ready as a string Q.

You want to stop the machine as soon as possible (even if Q is not fully made) and the string Q should have S1 as a subsequence at that moment when the machine is stopped.

Notes

• A subsequence is a sequence that can be derived from
• 1-based indexing is used.

Task

Determine what is earliest time (in seconds) after which the machine
can be stopped such that the string Q has S1 as a subsequence. Print -1 if it is not possible.

Example

Assumptions

• N=3

• S1= "abc"

• M=5

• S2="adbec"

•P={1,4,3,5,2}

Approach

String Q is initially”* * * * *”

• P[1] = 1, after first second, 1^st character is added, Q = "a*****”

• P[2] = 4, after second second, 4th character is added, Q =

Function description

Complete the solve function provided in the editor. The function takes the following 5 parameters and returns the final answer:

• N: Represents the length of S1

• S1: Represents the string S1

•  M: Represents the length of S2

•  S2: Represents the string S2

• P: Represents the permutation array for making the string Q

Input format

Note: This is the input format that you must use to provide custom input (available above the Compile and Test button).

The first line contains an integer T denoting the number of test cases. T also denotes the number of times you have to run the solve function on a different set of inputs.

For each test case:

• The first line contains a single integer N denoting the length of S1.
• The second line contains the string S1.

Constraints

1≤T≤10^5
1 ≤ N, M≤ 10^5
1≤ P[i]≤ M
The strings S1 and S2 consist of lowercase English characters only.
Sum of N over all test cases ≤ 5 * 10^5
Sum of M over all test cases ≤ 5 * 10^5

Sample Input

2
3
a b c
5
adcbe
1 4 3 5 2
3
abc

Sample output
-1
4