问题明确 #

给定仅由'M'和'L'组成的字符串，允许将任意字符在'M'和'L'间转换，求修改后最长连续'M'的长度恰好等于K所需的最少修改次数。

比如示例输入：S="MLMMLLM"，K=3，答案是1——修改索引4的'L'为'M'，得到"MLMMMLM"，此时最长连续'M'正好是3。

核心思路 #

要达成“最长连续'M'恰好为K”，我们需要：

1. 选定一段长度为K的区间，把这段区间里的所有'L'改成'M'（这是基础修改成本）；
2. 确保这段区间的左右两侧不能有连续的'M'——否则修改后这段区间会和左右的'M'连成更长的序列，导致最长长度超过K。如果左右紧邻的字符是'M'，我们需要额外修改它为'L'，增加一次成本。

简单来说，就是用滑动窗口遍历所有可能的K长度区间，计算每个区间对应的总修改成本，最后取最小值。

具体实现步骤 #

1. 前缀和预处理（快速计算窗口内的修改次数）

首先构建一个前缀和数组prefix，其中prefix[i]表示字符串前i个字符（索引0到i-1）中'L'的数量。这样任意区间[left, left+K-1]内的'L'数量（也就是把这段改成全'M'的修改次数）可以用prefix[left+K] - prefix[left]快速算出，避免每次遍历窗口都统计字符，提升效率。

2. 遍历所有K长度窗口，计算总修改成本

对于每个起始索引为left的窗口（left的范围是0 <= left <= len(S)-K）：

• 基础成本：base_cost = prefix[left+K] - prefix[left]（把窗口内所有'L'改成'M'的次数）；
• 左侧额外成本：如果left > 0且S[left-1] == 'M'，说明左边紧邻的是'M'，修改后会和窗口的'M'连成更长序列，需要把这个'M'改成'L'，所以base_cost += 1；
• 右侧额外成本：如果left+K < len(S)且S[left+K] == 'M'，同理，需要把这个'M'改成'L'，base_cost += 1；
• 特殊情况：如果字符串长度正好等于K，那么不需要考虑左右额外成本，直接取base_cost即可（因为整个字符串都是'M'，最长就是K）。

3. 取所有窗口成本的最小值

遍历完所有窗口后，最小的那个成本就是答案。

示例验证 #

拿题目中的示例S="MLMMLLM"（长度7），K=3来验证：

• 前缀和数组prefix为：[0,0,1,1,1,2,3,3]；
• 遍历窗口：
  • 当left=2时，窗口是索引2-4（字符'M','M','L'），基础成本是prefix[5]-prefix[2] = 2-1=1；
  • 左侧是索引1（字符'L'），无需额外修改；右侧是索引5（字符'L'），也无需额外修改；
  • 总成本为1，这就是最小的修改次数，符合示例结果。

特殊情况处理 #

• 当K=len(S)：直接计算把所有'L'改成'M'的次数即可，因为修改后最长就是K；
• 当字符串全为'M'且K < len(S)：需要修改左右的'M'为'L'，确保最长连续'M'是K，比如S="MMMM"，K=2，最小成本是1（修改一个外侧的'M'为'L'）；
• 当K=0：题目通常不会出现这种场景，若出现则需将所有'M'改为'L'，修改次数为字符串中'M'的总数。

内容的提问来源于stack exchange，提问作者Gagan Deep