Back to Leetcode

Readme

Binary_Search/3639.Minimum-Time-to-Activate-String/Readme.md

latest700 B
Original Source

3639.Minimum-Time-to-Activate-String

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

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