Sequential String
Snowflake● MediumINTERNOAProblem statement
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
countMinimumCharacters(s: String, arr: String[]) → int[]
Complete the function countMinimumCharacters in the editor below.
countMinimumCharacters has the following parameters:
String s: the special string of lengthnString[] 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
Examples
Example 1
s = "064819848398"arr = ["088", "364", "07"]return = [7, 10, -1]
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 <= 105
- 1 <= q <= 2*104
- 1 <= sum of the lengths of strings in arr <= 5*105
- All strings consist of characters '0'-'9' only.