Salesforce OA 删一种字母：最少无重复字符分段

题意与假设

这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。

• 题面要求恰好选一个英文小写字符并删除它的全部出现，而非删单个位置；输入非空且长度不超过 2×10^5。训练代码额外兼容空输入并返回 0。若只有一种字符，删除后空串在训练版需要 0 个 segment。
• segment 是连续非空子串，内部每个字符最多出现一次；所有 segment 按原序拼回删除后的字符串。公开题面把字母表限定为 26 个小写英文字母，训练代码的通用字符扫描只是实现范围更宽。
• 只返回最少段数，不返回被删字符或具体划分；并列删除方案任意。题目未说明空串是否可作为结果，文章把它列为训练约定。

解题路线

1. 枚举输入中出现的每一种字符 c；过滤 c 后，问题变成把剩余字符按原序划分为最少的‘段内不重复’连续子串。尽管题面可选择一个未出现的小写字母，那相当于不改变原串；删去某个已出现字符不会让最优段数比原串更大（原最优分段删字后仍各段合法），因此不影响最小答案。
2. 对固定 c 从左到右贪心：当前段的 seen 里没有下一字符就继续放入；若已出现，必须在该字符之前切段，因为不切会违反唯一性。尽量延长当前合法段不会增加未来的必要段数，可以通过交换/最远前缀论证。
3. 每个候选 c 扫描原串一次，计算段数后取最小。若所有字符都被删，seen 为空且段数保持 0；这样区分空串与一个非空段。

手动走一遍

avcccde：删 c 后得到 avde，所有字符互异，1 段；若不删 c，会在第二个 c 前切段，但训练版要求选一种删除。字符串 abac 删 a 后得到 bc，答案 1；字符串 aaa 删 a 后为空，按训练约定答案 0。

Python 参考实现

下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。

代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。

def min_unique_segments_after_one_letter_removal(text: str) -> int:
    """Remove all copies of one character type; minimize unique-char segments."""
    if not text:
        return 0
    best = len(text)
    for removed in set(text):
        segments = 0
        seen: set[str] = set()
        for char in text:
            if char == removed:
                continue
            if char in seen:
                segments += 1
                seen.clear()
            seen.add(char)
        if seen:
            segments += 1
        best = min(best, segments)
    return best

复杂度

n 为字符串长度、σ≤26 为不同字符数。候选最多 26 个，每次线性扫描与集合操作，时间 O(26n)，在本题固定字母表下即 O(n)；单次扫描辅助空间 O(26)，输出只有整数。

易错点与追问

容易失分的边界

• 把‘删除一种字母’当成只删除其中一个出现位置，例子中的三个 c 就无法同时消失。
• 重复字符出现时在其后切段，旧段已含两个相同字符，不合法。
• 把空结果计成 1 个非空 segment；需要先确认原题是否允许删到空串。
• 只尝试删除出现次数最多的字符；次数多不保证减少最多分段，须验证所有候选。

继续深挖

• 若必须恰好删一次字符出现位置而不是一种字符类型，状态与候选数都变化，需重读题干。
• 若还要输出被删字母和划分方案，记录最优候选，第二遍按贪心边界构造段。
• 若允许删除 k 种字符，在小字母表上可枚举组合或做状态压缩；不能把单字符枚举复杂度直接沿用。