寻找最大的 k，使得在对长度大于等于 k 的子字符串应用按位取反后能够得到一串 1。

Question

你可以选择一个长度大于等于k的子串，并对其进行按位取反。答案是允许从初始字符串得到一串1的最大k值。

对于如何解决这个问题，有什么想法吗？

- fragrantmonk

---

@Ripi2 根据定义，它不能由非连续字符组成。 - undefined

@Ripi2 我猜可以通过使用线段树来检查某个 k 是否合适，只需反转子字符串中0的数量超过1的情况。但我怀疑为每个 k 构建一个新的树是否足够高效。 - undefined

你如何手动解决这个问题？你能设计一个暴力的方法吗？例如，从 k=n 开始测试所有位置为 '1' 或否定整个字符串。如果不行，尝试所有 k=n-1 的子字符串，依此类推。 - undefined

对我来说，你在这里所谓的位取反不太清楚。你能提供一个例子吗？ - undefined

@Ripi2 我画了一点，并注意到一件事：以0111为例： 0111 ----\n

---

--

-- --

• • • 明白我的意思吗？如果我们可以选择某些线条，使得每个1下面有偶数条线并且每个0下面有奇数条线，那么我们可以将k作为最短所需线条长度。在这种情况下，k = 2，因为我们选择了以下线条组合 0111

---

---

• • • • - 但是我不知道如何用代码实现它...

- undefined

Answer 1

假设i和j是两个具有不同状态（true和false）的索引。如果k足够大，以至于i和j都在字符串的两端距离k之内，那么就没有办法使它们同时为true。因此，k必须足够小，以便对于每一对不匹配的位，只需翻转其中一个。

如果问题是找到一个适用于任意长度为n的字符串的k值，可以使用k=ceil(n/2)。通过使用大小为k的滑动窗口来翻转位，很容易使一半的位都相同，一旦完成这一步骤，可以使用更大的窗口来修复剩余的位。一旦所有位都相同，根据需要进行翻转或不翻转。

例如，1010100101，n=10，所以我们使用k=5。

I'll mark flipped bits in brackets
 1 0 1 0 1 0 0 1 0 1
 1[1 0 1 0 1]0 1 0 1
 1 1[1 0 1 0 1]1 0 1
 1 1 1[1 0 1 0 0]0 1
 1 1 1 1[1 0 1 1 1]1
Now that the left half is identical, we'll start using larger ranges
[0 0 0 0 0]0 1 1 1 1]
...and we finish with:
[1 1 1 1 1 1]1 1 1 1 

我们可以在左边和右边都与k相距的区域内，如果这两个区域是相同的，那么就可以使用k > n/2的条件。否则，我们就不能使用这个条件。后者很明显，因为每次翻转都必须包括所有这些位，所以如果它们不匹配，它们将永远保持不匹配。

如果重叠区域是相同的，按照上述方法从左边开始进行。

例如，0100000001。在这个例子中，我们可以使用k=8，因为从左边数第8位和从右边数第8位的交集是相同的。

 0 1 0 0 0 0 0 0 0 1
[1 0 1 1 1 1 1 1]0 1
 1[1 0 0 0 0 0 0 1]1
 1 1[1 1 1 1 1 1 0 0]
 Now that we have k 1s from one edge, we expand our flipping area as before
[0 0 0 0 0 0 0 0]0 0
[1 1 1 1 1 1 1 1 1 1]
...and we're done.

- Dave

---

既然你只需要最大的k值，那就取n/2加上以中心为半径的相同元素的个数。 - undefined