题目链接

吃豆人

题目描述

给定一个由小写字母组成的字符串，你每次可以替换其中一个字母。求最少需要替换多少次，才能使字符串中不包含 "pacman" 作为子串。

解题思路

本题要求的是消除所有 "pacman" 子串的最小操作次数。这是一个可以运用贪心策略解决的问题。

1. 核心观察

  • 操作成本：要破坏一个 "pacman" 子串，我们只需要修改其 6 个字符中的任意一个。因此，消除一个 "pacman" 子串的成本是 1 次替换。
  • 子串独立性：目标子串 "pacman" 有一个重要的性质——它没有自重叠。这意味着，字符串 "pacman" 的任何真前缀（如 "p", "pa", ...）都不等于它的任何真后缀（如 "n", "an", ...）。这个性质保证了在一个长字符串中，任意两个 "pacman" 的出现都是完全分离、互不重叠的。
  • 结论：由于每个 "pacman" 子串都是独立的，一次替换操作最多只能消除一个 "pacman" 子串。因此，最小替换次数等于字符串中 "pacman" 子串出现的总次数。

2. 贪心算法

基于以上结论，问题就简化为如何高效地计算不重叠的 "pacman" 子串的数量。我们可以使用一个贪心算法来解决：

  1. 从字符串的第一个字符开始，向后扫描。
  2. 在当前位置 i，检查从 i 开始的长度为 6 的子串是否等于 "pacman"。
  3. 如果等于：
    • 我们找到了一个 "pacman" 子串。将计数器加一。
    • 因为我们已经处理了这 6 个字符，并且知道下一个 "pacman" 不可能在这 6 个字符内开始，所以我们可以安全地将扫描指针向前跳过 6 个位置，从 i + 6 继续搜索。
  4. 如果不等于：
    • 说明当前位置不是 "pacman" 的起点。我们将扫描指针向前移动一位，从 i + 1 继续搜索。

重复这个过程直到扫描完整个字符串，最终的计数值就是所需的最少替换次数。

代码

#include <bits/stdc++.h>

using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    cin >> n;
    string s;
    cin >> s;

    int replacements = 0;
    int i = 0;
    while (i <= n - 6) {
        if (s.substr(i, 6) == "pacman") {
            replacements++;
            i += 6;
        } else {
            i++;
        }
    }

    cout << replacements << 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 replacements = 0;
        int i = 0;
        while (i <= n - 6) {
            // In Java, substring's end index is exclusive
            if (s.substring(i, i + 6).equals("pacman")) {
                replacements++;
                i += 6;
            } else {
                i++;
            }
        }
        System.out.println(replacements);
    }
}

import sys

def solve():
    n = int(sys.stdin.readline())
    s = sys.stdin.readline().strip()
    
    replacements = 0
    i = 0
    while i <= n - 6:
        if s[i:i+6] == "pacman":
            replacements += 1
            i += 6
        else:
            i += 1
            
    print(replacements)

solve()

算法及复杂度

  • 算法：贪心扫描
  • 时间复杂度：，其中 是输入字符串的长度。我们的扫描指针 i 只会从左到右移动一次。
  • 空间复杂度：，用于存储输入的字符串。算法本身只需要常数级别的额外空间。