FastPrep

Description

Solutions

Anti-Aging Serum

🤘 INTERN📚RELATED PROBLEMS

Rick is trying to create an anti-aging formula, which consists of sequence of different molecules (represented by lowercase alphabets here). The longer the sequence, the more effective the formula. He has been visiting different universes to get samples of the chemical for his experiments.

However, due to the struggle between the molecules, the formula becomes unstable if the length of the molecules is more than the tolerance of a molecule in the formula.

Each sample is a string of length n, having lowercase alphabetical characters. For each sample, determine the length of the most effective formula.

Note: The sequence can be a substring only for that sample.

Input Format:

The first line contains n, The number of universes.

Now for each Universe:

The first line contains m, the number of samples.

The next line contains a lowercase alphabetical string of length n.

The next line contains 26 integers a_j, 1 <= a_j <= 10^3, representing the maximum length of the substring in which each character can exist.

Output Format:

Print N lines, where each line has an integer stating the length of the longest sequence.

Example 1:

Input:  sample = "baaaccc", tolerance = [6, 4, 6, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
Output: 6 
Explanation:
      
      The longest substring is aaccc, where a can exist in a string of size 6, the same as c.

Example 2:

Input:  sample = "abcbddba", tolerance = [4, 7, 5, 5, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
Output: 5 
Explanation:
      
      The longest substring is bcbdd.

Constraints:

Number of universe n <= 10^5.

Sample length of each universe, m <= 10^3.

The sum of samples in each universe <= 10^6.