FastPrep

Description

Solutions

Sequential String

🤘 INTERN📚RELATED PROBLEMS

A special string of length n consists of characters 0-9 only. Its characters can only be accessed sequentially i.e the first '1' chosen is the leftmost '1' in s. There is an array arr of m strings, also consisting of characters 0-9. Calculate the minimum number of characters needed from s to construct a permutation of each of the strings in arr.

Return an array of integers where the ith element denotes the minimum length of a substring that contains a permutation of the ith string in arr. If a string cannot be constructed, return -1 at that index.

Function Description

Complete the function countMinimumCharacters in the editor below.

countMinimumCharacters has the following parameters:

String s: the special string of length n
String[] arr: an array of strings

Returns

int[]: an array of integers where each element denotes the minimum length of a substring needed to construct a permutation of the string at that index in arr, or -1 if it cannot be constructed

Example 1:

Input:  s = "064819848398", arr = ["088", "364", "07"]
Output: [7, 10, -1] 
Explanation:
Consider n=12, s="064819848398", m=3, arr=["088", "364", "07"]:
    
To construct "088", access the first 7 characters ("0648198") of the special string and use only '0', '8', and '8'. Since the characters can be rearranged, the result is "808".

To construct "364", access the first 10 characters ("0648198483") of the special string and use only '6', '4', and '3'. Rearrange to match "364".

String "07" cannot be constructed from the special string. No '7' is available.

The return array is [7, 10, -1]. Note that only bolded characters are used to construct the strings.

Constraints:

1 <= n <= 10⁵

1 <= q <= 2*10⁴

1 <= sum of the lengths of strings in arr <= 5*10⁵

All strings consist of characters '0'-'9' only.