吃豆人

[题目链接](https://www.nowcoder.com/practice/1741b982e50248b4bbbf24dfaab0fc84)

思路

题目要求：给定一个只含小写字母的字符串，每次操作可以把其中一个字母替换成另一个字母，问最少需要多少次操作才能让字符串中不再包含 "pacman" 这个子串。

先想一个简单的情况：如果字符串里只出现了一次 "pacman"，那显然只需要改掉其中任意一个字符就行，答案是 1。

那如果出现了多次呢？关键在于这些出现可能重叠。比如 "pacmanacman"，"pacman" 出现在位置 0，而如果我们把位置 5 的 'n' 改掉，就同时破坏了从位置 0 开始的这次匹配。之后从位置 6 往后扫描，不会再出现新的 "pacman"，所以答案还是 1。

贪心策略

从左到右扫描字符串，一旦发现 s[i..i+5] 恰好等于 "pacman"，就把答案加 1，然后直接跳到 i+6 的位置继续扫描。

为什么这样是对的？当我们在位置 $i$ 找到一个 "pacman" 时，我们必须至少改一个字符来消灭它。改完之后，这 6 个位置中至少有一个已经不是原来的字符了，所以任何完全包含在 $[i, i+5]$ 范围内的匹配都被破坏了。而 "pacman" 长度为 6，下一个可能的新匹配最早从 $i+1$ 开始，最晚到 $i+6$ 结束——但只要我们改的是这 6 个字符中的任意一个，从 $i$ 到 $i+5$ 范围内开始的所有匹配都会被影响。因此直接跳 6 格不会遗漏任何需要额外操作的情况。

换个角度理解：这本质上是一个区间覆盖问题。每个 "pacman" 出现占据长度为 6 的区间，我们要用最少的"一次替换"来"击穿"所有区间。贪心地每次处理最左边未被覆盖的匹配，跳过整个区间长度，就是经典的区间调度最优解。

代码

C++
Java
Python3
JavaScript

#include <bits/stdc++.h>
using namespace std;
int main(){
    int n;
    cin >> n;
    string s;
    cin >> s;
    int ans = 0;
    int i = 0;
    while(i <= n - 6){
        if(s.substr(i, 6) == "pacman"){
            ans++;
            i += 6;
        } else {
            i++;
        }
    }
    cout << ans << endl;
    return 0;
}

import java.util.Scanner;
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        String s = sc.next();
        int ans = 0;
        int i = 0;
        while (i <= n - 6) {
            if (s.substring(i, i + 6).equals("pacman")) {
                ans++;
                i += 6;
            } else {
                i++;
            }
        }
        System.out.println(ans);
    }
}

n = int(input())
s = input()
ans = 0
i = 0
while i <= n - 6:
    if s[i:i+6] == "pacman":
        ans += 1
        i += 6
    else:
        i += 1
print(ans)

const readline = require('readline');
const rl = readline.createInterface({ input: process.stdin });
const lines = [];
rl.on('line', line => lines.push(line.trim()));
rl.on('close', () => {
    const n = parseInt(lines[0]);
    const s = lines[1];
    let ans = 0;
    let i = 0;
    while (i <= n - 6) {
        if (s.substring(i, i + 6) === "pacman") {
            ans++;
            i += 6;
        } else {
            i++;
        }
    }
    console.log(ans);
});

复杂度分析

时间复杂度： $O(n)$ ，每个字符最多被访问常数次。
空间复杂度： $O(n)$ ，存储输入字符串。