Readme

3399.Smallest-Substring-With-Identical-Characters-II

容易发现，只要操作次数越多，就越容易将最长的identical-chracter sbustring长度降下来，所以很明显适合二分搜值的框架。

于是问题转变成给定一个len，问是否能在numOps次flip操作内，使得s里不存在超过长度len的identical substring。

我们将原字符串里进行预处理，分割为一系列由相同字符组成的子串。对于任意一段长度为x的子串，我们至少需要做多少次flip呢？很明显，贪心思想就可以得到最优解，即每隔len个字符，我们就做一次flip。假设最少做t次flip，我们需要满足

x <= (len+1) * t + len 

才能保证x里面不会有超过长度为len的identical substring。于是求得t>=(x-k)/(k+1)。不等式右边是小数时，取上界整数。

但是此题有一个坑。如果len是1的话，那么当x是偶数时，会给下一段x带来困扰。比如说s=00001111，我们在处理第一段0000时，会得到贪心的做法做两次flip使得其变成0101。我们发现这样的话下一段的1111其实需要处理的长度是5，给算法带来了极大的不便。比较简单的处理方法就是对len=1的情况特别处理，跳出之前的思维模式，只要考虑将s强制转换为01相间的字符串，计算需要做的flip即可。

那为什么len是2的时候我们就不用担心呢？距离s=000111，如果按照贪心的做法，对于第一段000我们需要做一次flip使得其变成001，似乎依然会影响到下一段的111. 但事实上，对于一段我们不需要变换成001，可以将最右端的1随意往左调动一下，变换成010。结果就是flip的次数不变的前提下，依然可以保证不会出现长度超过2的identical substring。注意，回顾一下二分搜值的框架，我们不要求一定要构造出长度为2的identical substring。

同理当len=3时，也不会出现类似影响下一段的困扰。之前的计算t的表达式依然可以适用。