Shortest Prefix for Each Target
MediumHash Map ยท Visa
Given a string s of digits and a list targets of digit strings, return a list with one integer per target: the length of the shortest prefix of s that contains every digit of the target at least as many times as the target does, or -1 if no prefix does.
The order of digits in a target does not matter.
Example 1
- Input:
- s = "3141592653", targets = ["51", "33", "99", "7"]
- Output:
- [5, 10, -1, -1]
- Explanation
- The prefix "31415" has one
1and one5. Only one9and no7ever appear, so those targets give-1.
Example 2
- Input:
- s = "0000", targets = ["00", "000000", "0"]
- Output:
- [2, -1, 1]
Example 3
- Input:
- s = "90210", targets = ["0012", "12", "9"]
- Output:
- [5, 4, 1]
Constraints
1 <= s.length <= 10^51 <= targets.length <= 10^41 <= targets[i].length <= 10^5, and the total length of all targets is at most10^5sand everytargets[i]contain only the characters0to9