题目描述

给你一个长度为 n 的二进制字符串 s 和一个整数 numOps。

你可以对 s 执行以下操作，最多 numOps 次：

• 选择任意下标 i（其中 0 <= i < n），并 翻转 s[i]，即如果 s[i] == '1'，则将 s[i] 改为 '0'，反之亦然。

你需要 最小化 s 的最长 相同子字符串 的长度，相同子字符串是指子字符串中的所有字符都相同。

返回执行所有操作后可获得的 最小 长度。

子字符串 是字符串中一个连续、 非空 的字符序列。

样例

输入: s = "000001", numOps = 1

输出: 2

解释: 

将 s[2] 改为 '1'，s 变为 "001001"。最长的所有字符相同的子串为 s[0..1] 和 s[3..4]。

输入: s = "0000", numOps = 2

输出: 1

解释: 

将 s[0] 和 s[2] 改为 '1'，s 变为 "1010"。

输入: s = "0101", numOps = 0

输出: 1

限制

• 1 <= n == s.length <= 10^5
• s 仅由 '0' 和 '1' 组成。
• 0 <= numOps <= n

算法

(二分答案，动态规划，单调队列) $O(n \log n)$

1. 在 字符相同的最短子字符串 I 的基础上，优化状态转移时间。
2. 注意到，状态转移方程可以写为 $f(i) = \min(g(j) - sum(j)) + sum(i)$，$g(i)$ 同理可以这样改写，所以可以将决策点 $j$ 维护在一个单调递增的队列中。
3. 其中队头永远是最优的转移点。每次需要先根据 $target$ 来更新队头。用最优决策转移后，再用新的状态更新队尾。最后新的状态进队。

时间复杂度

• 二分答案的上下界为 $[1, n]$。
• 每次判定动态规划的状态数为 $O(n)$，转移时间为常数且每个决策点最多进队一次，出队一次，故时间复杂度为 $O(n)$。
• 故总时间复杂度为 $O(n \log n)$。

空间复杂度

• 需要 $O(n)$ 的额外空间存储前缀和数组，动态规划的状态和单调队列。

C++ 代码

const int N = 100010;

class Solution {
private:
    int sum[N], f[N], g[N];
    int qf[N], qg[N];
    int hf, tf, hg, tg;

public:
    int minLength(string s, int numOps) {
        const int n = s.size();

        sum[0] = 0;
        for (int i = 1; i <= n; i++)
            sum[i] = sum[i - 1] + s[i - 1] - '0';

        f[0] = g[0] = 0;

        auto check = [&](int target) {
            hf = tf = hg = tg = 0;
            qf[tf++] = 0; qg[tg++] = 0;

            for (int i = 1; i <= n; i++) {
                while (hf < tf && i - qf[hf] > target)
                    ++hf;

                while (hg < tg && i - qg[hg] > target)
                    ++hg;

                f[i] = g[qg[hg]] + sum[i] - sum[qg[hg]];
                g[i] = f[qf[hf]] + (i - qf[hf]) - (sum[i] - sum[qf[hf]]);

                while (hf < tf && f[i] - i + sum[i] <=
                    f[qf[tf - 1]] - (qf[tf - 1]) + sum[qf[tf - 1]]
                )
                    --tf;

                while (hg < tg && g[i] - sum[i] <=
                    g[qg[tg - 1]] - sum[qg[tg - 1]]
                )
                    --tg;

                qf[tf++] = i; qg[tg++] = i;
            }

            return min(f[n], g[n]) <= numOps;
        };

        int l = 1, r = n;
        while (l < r) {
            int mid = (l + r) >> 1;
            if (check(mid)) r = mid;
            else l = mid + 1;
        }

        return l;
    }
};