小果的键盘

题意

给定一个只含 V 和 K 的字符串。最多修改一个字符，问修改后字符串中最多有多少个相邻子串 VK。

思路

因为 n <= 100，可以直接枚举所有可能：

先统计原字符串里的 VK 数量。
对每个位置，尝试把 V 改成 K，或把 K 改成 V。
统计修改后字符串里的 VK 数量，更新最大值。

这个枚举本身就是足够快、足够清楚的正解，不单独创建 brute.py。

Python 知识

/home/rainboy/mycode/hugo-blog/content/program_language/python/input_output_and_strings.md：字符串切片 text[i:i+2] 适合检查相邻两个字符。
/home/rainboy/mycode/hugo-blog/content/program_language/python/brute_force_validation.md：小范围枚举每个候选修改位置，是常见验证和解题方式。
字符串不可原地修改，所以先转成 list(s)，改完后 "".join(...) 转回字符串。

代码

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19def count_vk(text):
    total = 0
    for i in range(len(text) - 1):
        if text[i:i + 2] == "VK":
            total += 1
    return total


n = int(input())
s = input().strip()

answer = count_vk(s)

for i in range(n):
    changed = list(s)
    changed[i] = "K" if changed[i] == "V" else "V"
    answer = max(answer, count_vk("".join(changed)))

print(answer)

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-07-27 00:00
 * update_at: 2026-07-27 00:00
 */

#include <bits/stdc++.h>
using namespace std;

char s[105]; // 原始字符串
int n;

// 统计字符串中 "VK" 子串的个数
int count_vk(char *str, int len) {
    int cnt = 0;
    for (int i = 0; i < len - 1; i++) {
        if (str[i] == 'V' && str[i + 1] == 'K') cnt++;
    }
    return cnt;
}

int main() {
    cin >> n >> s;
    int ans = count_vk(s, n);
    // 枚举修改每个位置
    for (int i = 0; i < n; i++) {
        char bak = s[i];
        s[i] = (s[i] == 'V') ? 'K' : 'V'; // 切换字符
        ans = max(ans, count_vk(s, n));
        s[i] = bak; // 恢复
    }
    cout << ans;
    return 0;
}

Pythonic 写法

itertools.pairwise 统计相邻 VK：

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15from itertools import pairwise

n = int(input())
s = input().strip()


def count_vk(text: str) -> int:
    return sum(a + b == "VK" for a, b in pairwise(text))


answer = count_vk(s)
for i, ch in enumerate(s):
    flipped = s[:i] + ("K" if ch == "V" else "V") + s[i + 1 :]
    answer = max(answer, count_vk(flipped))
print(answer)

复杂度

枚举 n 个修改位置，每次统计需要 $O(n)$ ，总时间复杂度是 $O(n^2)$ 。n <= 100，可以轻松通过。空间复杂度是 $O(n)$ 。

总结

遇到“最多改一个位置”且数据很小的字符串题，直接枚举每个修改位置通常最稳。

目录

题意

思路

Python 知识

代码

Pythonic 写法

复杂度

总结