Shortest Digit Prefix for Target Multisets
Visa● MediumNEW GRADOAProblem statement
Given a digit string digits and an array targets, return one answer per target.
The answer is the minimum prefix length of digits whose characters contain every digit of the target with at least the same multiplicity. Prefix characters that are not used by the target may be ignored, so the target may be rearranged into any permutation.
Return 0 for an empty target and -1 when the full source string lacks a required occurrence.
Function
shortestDigitPrefixes(digits: String, targets: String[]) → int[]Examples
Example 1
digits = "012340221"targets = ["20","42","111","9"]return = [3,5,-1,-1]Each answer is the latest required occurrence among that target's digits; the source has too few ones and no nine for the final targets.
Example 2
digits = "777"targets = ["","7","77","777"]return = [0,1,2,3]The empty target needs no characters, while repeated sevens need successive occurrences.
Example 3
digits = "314159"targets = ["95","13","66"]return = [6,2,-1]Excess prefix digits may remain unused.
Constraints
0 <= digits.length <= 200000.1 <= targets.length <= 100000.- All strings contain only characters
0through9. - The combined target length is at most
200000.