更新题目最短前缀拼出 target

题目 visa-shortest-prefix-cover · 修改（rev 3） · cc · 2026-10-26 23:11
body

@@ -1,13 +1,42 @@
 ## 题目
 
-给一个只含数字 0–9 的字符串 s，和一组同样由数字组成的字符串 targets。对每个 target，求 s 从下标 0 开始的最短子串（也就是最短前缀）的长度，使这个前缀里的字符能拼出 target 的任意一种排列。返回一个长度数组。
+给一个只含数字 0–9 的字符串 `s`，和一组同样由数字组成的字符串 `targets`。对每个 target，求 `s` 从下标 0 开始的最短子串（也就是最短前缀）的长度，使这个前缀里的字符能拼出 target 的任意一种排列。返回一个长度数组，第 i 个数对应 `targets[i]`。
+
+「能拼出 target 的排列」只看个数，不看顺序：前缀里每种字符的个数都不少于 target 里这种字符的个数，就能拼出来。
+
+例子：`s = "1231"`，`targets = ["21", "11", "4", "1123"]`，返回 `[2, 4, -1, 4]`。
+
+- `"21"` 要一个 `1`、一个 `2`。前缀 `"12"`（长度 2）已经各有一个。
+- `"11"` 要两个 `1`。`s` 里第二个 `1` 在下标 3，前缀要取到 `"1231"`，长度 4。
+- `"4"` 要一个 `4`，`s` 里没有，无解，返回 -1。
+- `"1123"` 要两个 `1`，同样要取到下标 3，长度 4。
+
+### 开写之前要问清楚的
+
+现有正文转述的题面没写下面几处。OA 没有人可问，按「默认答案」一列写，并在代码注释里写明假设。这一列是按题面字面意思推断的，整列标【推断】。
+
+| 要问什么 | 默认答案【推断】 | 答案不同时代码怎么改 |
+| --- | --- | --- |
+| 某种字符在 `s` 里不够，无解时返回什么 | -1 | 改常量 `NOT_FOUND` |
+| target 是空串时返回什么 | 0，空前缀就能拼出空串 | 要求至少返回 1 之类的，在 `shortest_cover_length` 开头特判 |
+| `s` 是空串 | 空 target 返回 0，其余返回 -1 | 不用改，索引是空字典 |
 
 ## 面经里怎么考的
 
-Visa 27NG 的 OA 第三题（2026-09，标为 intermediate）。题面说「构造出 target 的所有排列」，意思就是前缀里每种字符的个数都不少于 target 里的个数。
+Visa 27NG 的 OA 第三题（2026-09，标为 intermediate）。按现有正文的转述，题面说「构造出 target 的所有排列」，读起来像要把每一种排列都构造出来。意思其实就是上面的个数条件：个数够了，任何一种排列都能拼出来，所以「所有排列」和「任意一种排列」是同一个条件。
 
 ## 思路
 
-先记下 s 里每种字符依次出现在哪些下标。target 需要字符 c 共 k 个，那么前缀至少要覆盖到 c 的第 k 次出现的位置。对 target 里的每种字符取这个位置的最大值，再加 1 就是答案；某种字符在 s 里不够 k 个就返回 -1（题面没写无解怎么办，考试时看题面）。
+朴素做法是对每个 target 从空前缀开始一个字符一个字符往后加，每加一个字符就检查一遍 target 要的每种字符够不够，第一次全够就停下。每个 target 最坏要扫完整个 `s`，总时间是 O(|s| × target 个数)。2026-10-26 实测，`s` 是 99999 个 `0` 加一个 `9`、target 全是 `"09"` 时，200 个 target 用了 10.4 秒，400 个用了 20.0 秒，耗时和 target 个数成正比。按这个比例推算（没有实测），1 万个 target 要 8 到 9 分钟。
+
+改进的关键一步是把「前缀够不够」换成一个下标比较。先把 `s` 里每种字符依次出现在哪些下标记下来，下面叫出现位置索引。比如 `s = "1231"` 时，`1` 出现在 `[0, 3]`，`2` 在 `[1]`，`3` 在 `[2]`。
+
+target 需要字符 c 共 k 个。长度为 L 的前缀覆盖下标 0 到 L-1，它里面至少有 k 个 c，等价于 c 的第 k 次出现（下标记作 p）落在前缀里，也就是 L ≥ p + 1。target 里每种字符都要满足这个条件，所以 L 要不小于所有这些 p + 1 中最大的那个，最短的 L 就取这个最大值。
+
+> [!say] For each character the target needs k times, the prefix must reach that character's k-th occurrence in s, so the answer is one plus the largest such index across the target's characters.
+
+某种字符在 `s` 里出现不到 k 次，任何前缀都不够，返回 -1。
+
+这样每个 target 只要数一遍自己的字符，再对每种字符查一次索引，不用再扫 `s`。索引是按字符建的字典，`s` 和 target 不限于数字时代码也不用改。
 
 ## 代码
@@ -16,27 +45,63 @@
 from collections import Counter, defaultdict
 
-def shortest_prefixes(s, targets):
-    pos = defaultdict(list)
-    for i, ch in enumerate(s):
-        pos[ch].append(i)
-    out = []
-    for t in targets:
-        ans = 0
-        for ch, c in Counter(t).items():
-            if len(pos[ch]) < c:
-                ans = -1
-                break
-            ans = max(ans, pos[ch][c - 1] + 1)
-        out.append(ans)
-    return out
+# 题面没规定的地方，按以下假设处理：
+# 1. 无解（某种字符在 s 里不够）返回 NOT_FOUND，即 -1。
+# 2. 空 target 返回 0。
+NOT_FOUND = -1
+
+
+def build_occurrence_index(s: str) -> dict[str, list[int]]:
+    """字符 -> 它在 s 里依次出现的下标，升序。"""
+    positions = defaultdict(list)
+    for index, ch in enumerate(s):
+        positions[ch].append(index)
+    return dict(positions)
+
+
+def shortest_cover_length(positions: dict[str, list[int]], target: str) -> int:
+    """s 的最短前缀长度，使前缀里每种字符的个数都不少于 target 里的个数。
+
+    target 为空时返回 0。某种字符在 s 里不够时返回 NOT_FOUND。
+    """
+    farthest = -1  # 前缀必须覆盖到的最大下标
+    for ch, need in Counter(target).items():
+        occurrences = positions.get(ch, [])
+        if len(occurrences) < need:
+            return NOT_FOUND
+        farthest = max(farthest, occurrences[need - 1])
+    return farthest + 1
+
+
+def shortest_prefixes(s: str, targets: list[str]) -> list[int]:
+    positions = build_occurrence_index(s)
+    return [shortest_cover_length(positions, target) for target in targets]
 ```
 
-本机和暴力解随机对拍过 300 组。
+建索引和回答单个 target 拆成两个函数，索引只建一次，所有 target 共用。`build_occurrence_index` 最后转成普通 `dict`，查不存在的字符用 `positions.get(ch, [])`，不会像 `defaultdict` 那样在查询时往字典里插入空列表。`farthest` 从 -1 开始，空 target 不进循环，直接返回 0。
+
+2026-10-26 在云端用 Python 3.13.17 跑了上面这段代码（原稿记录本机还和暴力解随机对拍过 300 组）。暴力解按定义写：长度从 0 往上试，每个前缀用 `Counter` 和 target 比个数。
+
+- 题目里的例子返回 `[2, 4, -1, 4]`。
+- 随机对拍：`s` 长 0 到 12、target 长 0 到 6，字符从 `0123` 里抽（种类少，重复字符多），每组 3 个 target，共 20000 组，和暴力解全部一致。
+- 上面那个最坏输入，1 万个 target 连建索引共约 0.02 秒（两次分别是 0.016 秒和 0.018 秒）。
 
 ## 复杂度
 
-预处理 O(|s|)，每个 target O(|target|)。逐个前缀去比计数会超时。
+建索引 O(|s|) 时间、O(|s|) 空间，每个下标恰好存一次。每个 target 用 O(|target|) 时间：`Counter` 数一遍，再对每种字符做一次字典查找和一次列表下标访问，都是 O(1)。总时间 O(|s| + 所有 target 长度之和)。
 
-## 英文讲法
+原题的数据范围现有正文没有记录，所以不能确定朴素做法在这道题上一定超时。按「思路」里的推算，`s` 长 10 万、target 有 1 万个时，朴素做法要好几分钟，OA 一道题的时限通常是秒级【推断】。
 
-> [!say] For each character the target needs k times, the prefix must reach that character's k-th occurrence in s, so the answer is one plus the largest such index across the target's characters.
+## 易错点
+
+- **忽略重复字符**：只看每种字符第一次出现的位置，把 target 当成字符集合，target 有重复字符时会少算。要取的是第 k 次出现，下标是 `occurrences[k - 1]`。下面是这个错误版本和正解在同一组输入上的结果（2026-10-26 实测，期望值来自暴力解），上面那 20000 组随机输入里它有 9438 组和暴力解不同。
+
+  | `s` | target | 暴力解 | 正解 | 忽略个数的版本 |
+  | --- | --- | --- | --- | --- |
+  | `"1231"` | `"21"` | 2 | 2 | 2 |
+  | `"1231"` | `"11"` | 4 | 4 | 1 |
+  | `"1231"` | `"1123"` | 4 | 4 | 3 |
+  | `"0000"` | `"00000"` | -1 | -1 | 1 |
+
+  `"11"` 那一行，错误版本只认第一个 `1`，返回 1，可前缀 `"1"` 只有一个 `1`，拼不出 `"11"`。`"00000"` 要 5 个 `0`，`s` 只有 4 个，它也照样返回 1。
+- **差一（off-by-one）**：下标从 0 开始，长度是最大下标加 1。
+- **空 target**：`farthest` 初值写成 0，空 target 会返回 1。初值取 -1，返回 0。
更新题目 最短前缀拼出 target

body

meta

更新题目最短前缀拼出 target
