小美的MT
美团 2024 春招第一场【技术】笔试编程题
题目描述
MT 是美团的缩写，因此小美很喜欢这两个字母。现在小美拿到了一个仅由大写字母
组成的字符串，她最多可以操作 k 次，每次可以修改任意一个字符。
小美想知道，操作结束后最多共有多少个 M 和 T 字符。
输入格式
第一行两个正整数 n、k，代表字符串长度和操作次数。 第二行一个长度为 n 的、仅由大写字母组成的字符串 s。
输出格式
输出操作结束后最多共有多少个 M 和 T 字符。
示例
示例 1
输入：
5 2
MTUAN
输出：
4
说明：
原来有 2 个目标字符（M、T），最多还能改 2 个字符，
把 U、N 改成 M、T，得到 MTTAM，共 4 个。
解题思路
第一步：理解问题本质
目标字符只有 M 和 T 两种。每次操作可以修改任意一个字符，
所以我们只关心两件事：
- 现在已经有几个字符是
M或T； - 还能改几次。
第二步：为什么可以贪心
每一次操作最多让「目标字符数」+1（把某个非目标字符改成 M 或 T）。
把操作浪费在别的改动上不会有任何好处，所以能改就改成目标字符。
设已有的目标字符数为 cnt，那么 cnt + k 就是理论上界。
第三步：别超过字符串长度
再怎么改，目标字符也不会超过 n 个（字符串一共就 n 个位置）。 所以答案是：
min(n, cnt + k)
完整代码实现
算法可视化 · 逐帧回放这道题的代码8 帧 · 录制输入
import sys
def solve() -> None:
"""统计 M/T 数量，再加上最多 k 次修改"""
data = sys.stdin.read().split()
if not data:
return
n = int(data[0])
k = int(data[1])
s = data[2]
cnt = sum(1 for ch in s if ch == 'M' or ch == 'T')
sys.stdout.write(str(min(n, cnt + k)) + "\n")
if __name__ == "__main__":
solve()
示例推演
以 n = 5, k = 2, s = "MTUAN" 为例：
| 位置 | 字符 | 是否 M/T |
|---|---|---|
| 1 | M | 是 |
| 2 | T | 是 |
| 3 | U | 否 |
| 4 | A | 否 |
| 5 | N | 否 |
已有 2 个，还能改 2 个 → 2 + 2 = 4，且 4 ≤ n = 5，所以答案是 4。
复杂度分析
| 解法 | 时间复杂度 | 空间复杂度 | 说明 |
|---|---|---|---|
| 一次遍历计数 | O(n) | O(1) | 推荐 |
易错点总结
1. 忘记和 n 取最小值
如果 k 很大（比如字符串里几乎没有 M/T），cnt + k 会超过 n。
必须写成 min(n, cnt + k)。
2. 把「修改」当成「交换」
题目是「修改任意一个字符」，可以直接把任意位置改成 M 或 T，
不存在「要拿一个已有的换」的约束。
3. 读输入的姿势
第一行是 n、k，第二行是字符串。用 sys.stdin.read().split() 拿到
["5", "2", "MTUAN"] 即可，字符串里没有空格。
扩展思考
- 如果目标字符从两个变成一个（只要
M），答案同样是min(n, cnt_M + k)。 - 如果限制「只能把相邻字符一起改」，就变成了区间 DP，难度完全不同。