更新题目 最短前缀拼出 target
题目 visa-shortest-prefix-cover · 修改（rev 4） · · 2026-10-27 00:33
body
@@ -32,5 +32,5 @@ 改进的关键一步是把「前缀够不够」换成一个下标比较。先把 `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 就取这个最大值。 +target 需要字符 c 共 k 个。长度为 L 的前缀覆盖下标 0 到 $L-1$，它里面至少有 k 个 c，等价于 c 的第 k 次出现（下标记作 p）落在前缀里，也就是 $L \ge 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. @@ -88,5 +88,5 @@ ## 复杂度 -建索引 O(|s|) 时间、O(|s|) 空间，每个下标恰好存一次。每个 target 用 O(|target|) 时间：`Counter` 数一遍，再对每种字符做一次字典查找和一次列表下标访问，都是 O(1)。总时间 O(|s| + 所有 target 长度之和)。 +建索引 $O(|s|)$ 时间、$O(|s|)$ 空间，每个下标恰好存一次。每个 target 用 $O(|target|)$ 时间：`Counter` 数一遍，再对每种字符做一次字典查找和一次列表下标访问，都是 $O(1)$。总时间 O(|s| + 所有 target 长度之和)。 原题的数据范围现有正文没有记录，所以不能确定朴素做法在这道题上一定超时。按「思路」里的推算，`s` 长 10 万、target 有 1 万个时，朴素做法要好几分钟，OA 一道题的时限通常是秒级【推断】。
meta
@@ -1,5 +1,5 @@ { "depth_guide": "2026-10-23", - "rewritten_by": "cloud:20261026-1620", + "rewritten_by": "cloud:20261026-2312", "rewritten_at": "2026-10-27" }