Readme

3639.Minimum-Time-to-Activate-String

非常明显的二分搜值。假设运行到某个时刻t，那么我们就得到一个包含若干星号的字符串。我们需要考察该字符串里至少包含一个星号的substring的个数是否超过k。超过的话，就可以尝试减少k，否则需要增加k。

计算“至少包含一个星号的substring的个数”，等效于反向计算“没有任何星号的substring的个数”，并且后者更容易计算。对于任何一段连续的、不包含任何星号的子串长度p，那么就有p*(p+1)/2个子串符合条件。我们分割原始字符串为若干段“没有任何星号的区间”，分别计算再相加即可。