第2题-避重口令

小红书9月13日机考题目与解析

短视频审核后台要把已过审成片的标题按发布时间依次拼接，得到小写字符串 $S$。$S$ 的每一个子序列（含 $S$ 本身与空串）都被视为已经占用的口令，不能再给新专题使用。

求最短的、不是 $S$ 子序列的小写口令长度。

子序列：从原串中删除任意个（可以为零个）字符后，剩余字符保持相对顺序所形成的串。

输入描述

一行，仅含小写字母的字符串 $S$（$1 \le |S| \le 10^5$）。

输出描述

一行一个正整数，即最短未占用口令的长度。

样例 1

输入：

zyxwvutsrqponmlkjihgfedcbazyxwvutsrqponmlkjihgfedcba

输出：

3

说明：$S$ 由两段倒序的 26 个小写字母拼接而成。任意单个字母、任意长度为 2 的小写串都是 $S$ 的子序列（前半段取第一个字符、后半段取第二个字符即可）。$S$ 中字母 a 只出现两次，故 aaa 不是子序列，最短长度为 3。

思路

要找最短的小写串 t，使得 t 不是 s 的子序列。若 s 里缺了某一种字母，则长度为 1 即可。若 26 种字母都出现过，任意长度为 1 的串都是子序列，答案至少为 2，并可以继续往下推。

从左到右扫描 s，用集合记录当前这一层已经见过的不同字母。每凑齐 26 种，就说明任意一个字符都能在这一层里被匹配掉，于是层数加一并清空集合。扫完后的层数加 1 就是答案。

正确性可以两边夹：设凑齐了 X 层。任意长度不超过 X 的串，第 j 个字符都可以在第 j 层里匹配，因而都是子序列。另一方面，记第 j 层最后补齐 26 种的那个字符为 c_j，最后一层之后的后缀里缺的某个字母为 d，则 c_1 c_2 ... c_X d 无法按顺序匹配，故存在长度为 X + 1 的非子序列。

实现方法：开一个大小为 26 的布尔数组（或集合）记录当前层见过的字母，再记一个计数器。扫到新字母就标记并加一；计数到 26 时答案加一、标记清空。最后输出答案（初始为 1）。

复杂度分析： 时间复杂度 O(|s|)；空间复杂度 O(26)，即常数空间。

贪心分块：从左往右扫描，每当凑齐全部 26 个字母就形成一个块并清空计数，设总共得到 $k$ 个块。

• 任何长度 $\le k$ 的串都是 $S$ 的子序列——第 $i$ 个字符总能在第 $i$ 个块里找到；
• 而 a 重复 $k+1$ 次不是子序列——每个块至多贡献一个 a。

所以答案为 $k + 1$，一次线性扫描即可。

代码

s = input().strip()
seen = set()
ans = 0
for ch in s:
    seen.add(ch)
    if len(seen) == 26:
        ans += 1
        seen.clear()

print(ans + 1)