Minimum Prefix Length to Form a Permutation

Problem Given a string s of digits and an array arr[] of digit strings, for each arr[i] compute res[i] = the length of the shortest prefix of s whose characters (as a multiset) cover all characters of arr[i]; -1 if the whole of s doesn't suffice.

Input / Output

• Input: string s, string[] arr (all chars '0'–'9').
• Output: int[] res.

Constraints

• |s| and total query length up to 10^5 — per-query rescans of s are fine only if bounded; precomputation makes queries O(alphabet).

Example

• s = "471247", arr = ["124"] → 4 (prefix "4712" covers {1,2,4}).

Expected approach

• Precompute prefix counts: cnt[i][d] = occurrences of digit d in s[0..i) — or, cleaner, pos[d][k] = index at which the kth copy of digit d appears. Per query: count needed digits; answer = max over digits d of pos[d][need_d] + 1 (-1 if any digit's supply runs short). O(10·|s|) precompute, O(10) per query. The naive two-pointer scan per query is the acceptable first cut; the position-table optimization is the differentiator.