找到最大 k，使得对长度 >= k 的子串进行按位求反后可以得到 1 的字符串

Question

您可以无限次选择长度 >= k 的子字符串并对它应用按位求反。答案是允许从初始字符串中得到一串 1 的最大 k。

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

Answer 1

假设 i 和 j 是两个具有不同状态的索引：true 和 false。如果 k 足够大，使得 i 和 j 都在字符串两端的 k 范围内，则无法使它们都为 true。因此 k 必须足够小，以便对于每一对不匹配的位，可以仅翻转其中一个。

如果问题是找到适用于任何长度为 n 的字符串的 k 值，请使用 k = n/2。通过使用大小为 k 的滑动窗口来翻转位，您可以轻松地使其一半完全相同，一旦完成，您可以使用更大的窗口来修复剩余的位。一旦所有位都相同，根据需要翻转或不翻转。

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

I'll mark flipped bits in brackets
 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 内的区域相同，我们就可以得到 k > n/2，否则就不能。后者很清楚，因为每次翻转都必须包含所有这些位，因此如果它们不匹配，它们将始终保持不匹配。

如果重叠区域相同，则从左侧开始按上述方式进行

例如0 1 0 0 0 0 0 0 0 1。这里我们可以使用k=8，因为左边8位和右边8位的交集是相同的。

[1 0 1 1 1 1 1 1]0 1
 1[1 0 0 0 0 0 0 1]0
 1 1[1 1 1 1 1 1 0 1]
 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 1
[1 1 1 1 1 1 1 1 1]1
...and we're done.