LeetCode 3398. 字符相同的最短子字符串 I — JavaScript 实现

思路

本题具有单调性：如果最长相同子串长度 `m` 可以实现，那么任何大于 `m` 的长度也一定可以实现。因此使用二分答案。

验证函数 `check(m)` 判断能否在 `numOps` 次翻转内，使最长连续相同子串长度不超过 `m`：

情况    策略    
`m == 1`    字符串必须变成交替的 `"0101..."` 或 `"1010..."`。分别计算两种模式需要的翻转次数，取最小值。    
`m > 1`    遍历字符串，统计每一段连续相同字符的长度 `k`。每隔 `m` 个字符翻转一次（即每 `m+1` 个位置翻一个），可将该段分割成长度均不超过 `m` 的块。所需翻转次数为 `⌊k / (m+1)⌋`。    

二分搜索区间为 `[1, n]`，寻找最小的可行 `m`。

- 时间复杂度：`O(n log n)`
- 空间复杂度：`O(1)`

代码

```javascript
/**
 * @param {string} s
 * @param {number} numOps
 * @return {number}
 */
var minLength = function(s, numOps) {
    const n = s.length;

    // 验证：能否在 numOps 次操作内，使最长连续相同子串长度不超过 m
    const check = (m) => {
        let cnt = 0; // 所需操作次数

        if (m === 1) {
            // 需要变成 "0101..." 或 "1010..."
            // 先计算变成 "0101..." 需要翻转几次
            for (let i = 0; i < n; i++) {
                const expected = (i % 2 === 0) ? '0' : '1';
                if (s[i] !== expected) {
                    cnt++;
                }
            }
            // 另一种 "1010..." 的翻转次数为 n - cnt，取最小值
            cnt = Math.min(cnt, n - cnt);
        } else {
            let k = 0; // 当前连续相同字符段的长度
            for (let i = 0; i < n; i++) {
                k++;
                // 到达段尾（字符串末尾或下一个字符不同）
                if (i === n - 1 || s[i] !== s[i + 1]) {
                    // 每隔 m 个字符翻一个，需要 k // (m + 1) 次操作
                    cnt += Math.floor(k / (m + 1));
                    k = 0;
                }
            }
        }

        return cnt <= numOps;
    };

    // 二分搜索最小可行值
    let left = 1, right = n;
    while (left < right) {
        const mid = (left + right) >> 1;
        if (check(mid)) {
            right = mid; // mid 可行，尝试更小
        } else {
            left = mid + 1; // mid 不可行，需要更大
        }
    }

    return left;
};
```

示例验证

- `s = "000001", numOps = 1`：二分最终找到 `m = 2`。`check(2)` 时，连续段 `"00000"` 长度 5，需要 `5 // 3 = 1` 次翻转，满足 `1 <= 1`，返回 2。
- `s = "0000", numOps = 2`：`check(1)` 时，变成 `"0101"` 需要 2 次翻转，满足 `2 <= 2`，返回 1。
- `s = "0101", numOps = 0`：`check(1)` 需要 0 次翻转，返回 1。