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

Quick Overview

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.

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

Company: Visa

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Online Assessment

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 ```python 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`.

Overview: 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 .

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

Quick Overview

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

Function Signature

Rules

Constraints

Examples

Submit Your Answer to Earn 20XP