FastPrep
Problem · String

Anti-Aging Serum

Learn this problem
● MediumRubrik logoRubrikINTERNOA

Problem statement

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.

    Function

    mostEffectiveFormula(sample: String, tolerance: int[]) → int

    Examples

    Example 1

    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]return = 6

    The longest substring is aaccc, where a can exist in a string of size 6, the same as c.

    Example 2

    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]return = 5

    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.

    • More Rubrik problems

    drafts saved locally
    public int mostEffectiveFormula(String sample, int[] tolerance) {
  // write your code here
}
    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]
    expected6
    checking account