Salesforce OA 相邻字符去重：最少替换次数与字符集边界

题意与假设

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

• 训练版允许把任意位置替换成不同于其左右邻居的字符，例如可使用输入之外的新字符；一次替换成本为 1，字符串长度不变。
• 每个单词独立计算，不需要输出替换后的字符串；空串和单字符答案都是 0。字符比较按 Python Unicode code point，组合字符或大小写归一化需另问。
• 如果替换字符被限制到固定小字母表，特别是仅两种字符，连续段公式可能失效；须取得完整字符集条件后改用 DP。

解题路线

1. 把字符串拆成极大连续同字符段。长度为 L 的一段有 L−1 条冲突相邻边；一次替换至多消除段内两条冲突边，因此至少需 floor(L/2) 次。
2. 可在该段的第 2、4、6… 个位置替换为与左右都不同的新字符，恰好用 floor(L/2) 次，并不与段外边界产生新冲突；故在训练版字符集假设下下界可达到。各段互不重叠，总答案为每段 floor(L/2) 之和。
3. 线性扫描维护当前字符与段长，遇新字符时把上一段贡献加入总数；结束时结算最后一段。只需计数，不必真的修改字符串。

手动走一遍

add 的 `dd` 长度 2，贡献 1；boook 的 `ooo` 长度 3，贡献 1；break 全为长度 1，贡献 0。`aaaa` 长度 4，至少改两个位置，可变成 `abab`（假设允许 b）。但若仅允许 a/b，`baab` 虽有一段 `aa`，一处替换无法同时避免两侧新冲突，真实最少要 2 次；这说明题目未明确的字符集约束不能省略。

Python 参考实现

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

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

def minimum_replacements(words: list[str]) -> list[int]:
    """Count edits assuming a replacement can use a fresh character."""
    answers = []
    for word in words:
        total = 0
        run = 0
        previous = None
        for char in word:
            if char == previous:
                run += 1
            else:
                total += run // 2
                previous, run = char, 1
        total += run // 2
        answers.append(total)
    return answers

复杂度

对所有输入串的总长度记为 N，扫描时间 O(N)；除输出数组外辅助空间 O(1)，输出自身占 O(W)，W 为单词数。若字符集受限而使用 DP，通常需按位置和末字符记状态，复杂度随允许字符种类增加。

易错点与追问

容易失分的边界

• 把每条相同相邻边都计为一次替换，会把 `aaa` 错算为 2；中间字符一改可同时打断两条边。
• 忘记结算字符串末尾的连续段，或在空串上强行初始化长度为 1。
• 未说明替换字符集便宣称 floor(L/2) 对所有情况成立；两字符限制下的 `baab` 是反例。
• 直接原地改字符但只看左邻，可能把修改后的字符变成与右邻相同。

继续深挖

• 若只能从给定字母表替换，建立 DP[i][last] 表示处理前 i 位、最后一个字符为 last 的最小代价；转移时 last 不能等于新字符。
• 若每个位置有不同替换代价，段长公式不再适用，可做路径上的最小权冲突修复 DP。
• 若需输出具体修改方案，选不与左右邻居冲突的字符并记录替换位置；不能只输出计数。