Katkat
Back

Shortest Prefix of a Digit String That Can Build Every Permutation of a Target

VisaSoftware Engineer · Online Assessment
MediumSoftware EngineerOnline AssessmentCoding & Algorithms

Last updated

Given a digit string and a list of digit targets, return for each target the length of the shortest prefix whose characters could build every permutation of that target, or -1 if no prefix can. It tests character frequency counting, precomputation over a string, and answering many queries efficiently.

You are given a string s made only of the digit characters '0' to '9', and a list of strings targets, each also made only of digit characters.

For each string target in targets, find the length of the shortest prefix of s (a substring of s that starts at index 0) whose characters can be used to build every permutation of target. Return these lengths as a list in the same order as targets.

Function Signature

def shortest_prefix_lengths(s: str, targets: list[str]) -> list[int]:

Rules

  • To build a string from a prefix, pick characters from the prefix and arrange them in any order. Each character position of the prefix can be used at most once within that one string.
  • Every permutation of target is built separately from the same prefix. The prefix does not need enough characters to build all of the permutations at the same time.
  • If no prefix of s, including s itself, can build every permutation of target, the answer for that target is -1.
  • Every target is answered independently, and s is never modified.

Constraints

  • 1 <= len(s) <= 100000
  • 1 <= len(targets) <= 100000
  • 1 <= len(targets[i]) <= 100000, and the total length of all strings in targets is at most 200000.
  • Every character of s and of every target is one of '0' to '9'.
  • Each element of the output is -1 or an integer from len(target) to len(s) inclusive, and it is uniquely determined by the input.

Examples

Example 1

  • Input: s = "1213321", targets = ["12", "113", "2233"]
  • Output: [2, 4, 6]
  • Explanation: The prefix "12" can build both "12" and "21". For "113", the prefix "121" has no 3, while "1213" can build each of "113", "131" and "311", so the answer is 4. For "2233", the prefix "12133" has only one 2, and "121332" is the first prefix that works, so the answer is 6.

Example 2

  • Input: s = "9080", targets = ["00", "000", "89", "7"]
  • Output: [4, -1, 3, -1]
  • Explanation: "00" needs the whole string "9080". "000" cannot be built even from all of s, which has only two zeros. "89" and "98" can both be built from "908". s contains no 7.