Skip to main content

Google

Google OA-13 2024

Problem Description

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.

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.
The sum of N over all test cases ≤ 5 * 10^5
The sum of M over all test cases ≤ 5 * 10^5

Sample Input:
2
3
abc
5
adcbe
1 4 3 5 2
3
abc

Sample Output:
-1
4