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.

Read the full Visa Software Engineer interview experience this question came from

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`. Implement `shortest_prefix_lengths(s, targets)`. **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. - The output has exactly one entry per target, in the same order as `targets` (duplicate targets get their own entries). Each entry is `-1` or an integer from `len(target)` to `len(s)` inclusive, and it is uniquely determined by the input. **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'`. - Every output value is at most `100000` in absolute value, so it fits in a 32-bit signed integer. **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`.

Constraints

  • 1 <= len(s) <= 100000
  • 1 <= len(targets) <= 100000
  • 1 <= len(targets[i]) <= 100000
  • 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 output value is -1 or an integer from len(target) to len(s) inclusive (fits in a 32-bit signed integer)

Examples

Input: ('1213321', ['12', '113', '2233'])

Expected Output: [2, 4, 6]

Input: ('9080', ['00', '000', '89', '7'])

Expected Output: [4, -1, 3, -1]

Hints

  1. Building every permutation of a target separately needs exactly the same characters as building the target once. Which property of the target actually matters?
  2. Only ten distinct characters can ever appear. For a single digit that the target needs k times, where is the shortest prefix that contains it k times?
  3. Precompute something about s once so that each target can be answered in time proportional to its own length, not to len(s).

Loading coding console...

Show the approach

Approach

All permutations of a target use the same multiset of characters, and they are built one at a time from the same prefix, so a prefix works exactly when, for every digit d, it contains at least as many copies of d as the target does. Prefix digit counts only grow as the prefix gets longer, so the shortest valid prefix is the first length at which every digit's requirement is met. For a digit d that the target uses k times, the requirement is first met right after the k-th occurrence of d in s. The reference therefore records, once, the list of indices at which each of the ten digits occurs in s. For each target it counts its digits; if some digit is needed more times than it appears in s the answer is -1, otherwise the answer is the maximum over the needed digits of (index of the k-th occurrence) + 1. Taking the maximum, not the sum or the first digit's position, is what makes every digit's requirement hold at once. Each target is processed independently, so duplicates and permutations of each other receive identical answers in their own positions.

Time complexity:
O(len(s) + T), where T is the total length of all targets
Space complexity:
O(len(s) + len(targets))