求最大k值：通过取长度≥k的子串取反得到全1字符串

要解决这个问题，我们可以通过分析字符串中0块的分布，结合差分翻转的逻辑转化为配对问题，最终求出最大k值。具体步骤如下：

步骤1：提取变化点序列 #

首先，我们需要找出字符串中字符从0变1或1变0的位置，结合差分翻转的逻辑生成完整的变化点列表：

• 初始化空列表points，假设初始状态为全1（对应差分初始值为0）。
• 遍历字符串，记录每一处字符变化的位置（从第1位开始计数）。
• 如果字符串最后一个字符是0，需要在列表末尾添加n+1（n为字符串长度），确保差分状态最终回到初始的全1状态。
• 最终points的长度为偶数，记为2m，其中m是原字符串中连续0块的数量。

步骤2：计算最大k值 #

• 如果m=0（即points为空，原字符串已经是全1）：最大k值为字符串长度n，因为无需任何操作即可满足要求。
• 如果m>0：
  1. 将points分为前m个和后m个元素，配对第i个元素和第i+m个元素（i从0到m-1）。
  2. 计算每对元素的差值points[i+m] - points[i]，取这些差值中的最小值min_diff。
  3. 这个min_diff就是能将字符串转化为全1的最大k值——因为每对差值对应一个合法的翻转区间长度，所有区间长度都≥min_diff，且无法找到更大的k满足所有配对的差值要求。

示例验证 #

举几个例子说明：

• 示例1：字符串010（n=3）
  • 变化点序列：[1,2,3,4]，m=2
  • 配对：(1,3)、(2,4)，差值分别为2、2，min_diff=2
  • 最大k=2，验证：翻转前2位得到100，再翻转后2位得到111，成功。
• 示例2：字符串1001（n=4）
  • 变化点序列：[2,4]，m=1
  • 配对：(2,4)，差值为2，min_diff=2
  • 最大k=2，验证：翻转中间2位直接得到1111，成功。
• 示例3：字符串01010（n=5）
  • 变化点序列：[1,2,3,4,5,6]，m=3
  • 配对：(1,4)、(2,5)、(3,6)，差值均为3，min_diff=3
  • 最大k=3，验证：翻转1-3位得到10110，翻转2-4位得到11000，翻转3-5位得到11111，成功。

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