FastPrep
Problem · String

Sequential String

Learn this problem
● MediumSnowflakeINTERNOA
See Snowflake hiring insights

Problem 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:

  1. String s: the special string of length n
  2. 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

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.

    • More Snowflake problems

    drafts saved locally
    public int[] countMinimumCharacters(String s, String[] arr) {
    // write your code here
}
    s"064819848398"
    arr["088", "364", "07"]
    expected[7, 10, -1]
    checking account