语言月赛 202408 因友情而终结
题意分析¶
给定一个仅由小写字母组成的字符串 $S$，可以对其执行任意次如下操作：
- 选择长度为 $4$ 的任意子串，并将其替换为字符串
love。
每次操作会替换字符串的一部分，目的是使字符串中不再包含子串 friend。题目要求计算达到这一目标所需的最少操作次数。
解题思路¶
核心目标是破坏掉所有出现的 friend 子串。
关键观察点：
- 子串
friend长度为 $6$。 - 每次操作可以替换任意连续的 $4$ 个字符。
- 替换后新的内容为
love，无论原来的 $4$ 个字符是哪些，都被改掉了。
因此，我们可以将本题转化为：
对每个出现的
friend子串，找到一个长度为 $4$ 的子串，使其覆盖这个friend，从而破坏它。 最佳破坏方案是从d开始往后连续 $4$ 个字符，替换为love。
策略：¶
- 从左到右扫描字符串，找到每一个
friend出现的位置。if(s.substr(i, 6) == "friend")
- 对于每一个
friend，选取尽量靠右的、长度为 $4$ 的子串去覆盖它的一部分。- 最优选择是：从位置
i + 5到i + 8的子串，其中i + 5是friend中d出现的位置。 - 这样可以一次性破坏该
friend，并影响后续最的字符。
- 最优选择是：从位置
该方法可以在一次遍历中完成，并保证使用最少的操作次数。
实现步骤¶
- 初始化计数器
ans = 0，定义int n = s.size()。 - 从左到右扫描字符串，
for (int i = 0; i < n; i++)： - 每次判断当前位置在内连续 $6$ 个字符是否是
friend。if(s.substr(i, 6) == "friend")
- 如果是，说明发现一个需要处理的
friend。- 计数器加一。
- 修改
s[i + 5], s[i + 6], s[i + 7], s[i + 8]为love。- 注意确保 $i+8<n$ 避免字符串越界。
- 重复上述过程，直到遍历完整个字符串。
时间复杂度分析¶
- 时间复杂度为 $O(n)$，其中 $n$ 是字符串长度。
- 因为只扫描一遍字符串，每次最多前进 6 步。
- 空间复杂度为 $O(1)$，只需要常数空间记录指针与计数器。
对于 $n \le 10^6$ 的数据规模，效率完全可接受。
总结¶
- 本题关键在于识别子串
friend并尽可能高效地破坏它。 - 利用替换操作影响 $4$ 个字符的特性，可以设计贪心策略，从左到右选择替换窗口。
- 保证所有
friend被破坏的同时，避免重复替换，达成最少操作次数。
该策略通过一次线性扫描即可完成，具有良好的时间和空间效率。