题目描述

给你一个长度为 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 <= 1000
• s 仅由 '0' 和 '1' 组成。
• 0 <= numOps <= n

算法

(二分答案，动态规划) $O(n^2 \log n)$

1. 让最大值最小的问题且满足单调性，可以用二分答案求解。
2. 假设最长相同子字符串的长度为 $target$，则需要判定是否能在 $numOps$ 内完成操作。
3. 设状态 $f(i)$ 表示前 $i$ 个字符串满足了条件，且最终是以 '0' 结尾的最少操作次数。同理，$g(i)$ 表示前 $i$ 个字符串满足了条件，且最终是以 '1' 结尾的最少操作次数。
4. 初始时，$f(0) = g(0) = 0$，其余为正无穷待定。
5. 转移时，对于第 $i$ 个字符，可以从 $j \in [i - target, i - 1]$ 转移，即 $[j + 1, i]$ 是一段相同的子字符串。枚举 $j$，然后转移将区间 $[j + 1, i]$ 修改为全 '0' 或者全 '1'。这可以通过预处理前缀和数组计算出转移代价。
6. 最终答案为 $\min(f(n), g(n))$。

时间复杂度

• 二分答案的上下界为 $[1, n]$。
• 每次判定动态规划的状态数为 $O(n)$，转移时间为 $O(n)$，故时间复杂度为 $O(n^2)$。
• 故总时间复杂度为 $O(n^2 \log n)$。

空间复杂度

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

C++ 代码

const int N = 1010;

class Solution {
private:
    int sum[N], f[N], g[N];

    inline int min(int x, int y) {
        return x < y ? x : y;
    }

    inline int max(int x, int y) {
        return x > y ? x : y;
    }

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) {
            for (int i = 1; i <= n; i++) {
                f[i] = g[i] = INT_MAX;
                for (int j = max(0, i - target); j < i; j++) {
                    f[i] = min(f[i], g[j] + sum[i] - sum[j]);
                    g[i] = min(g[i], f[j] + (i - j) - (sum[i] - sum[j]));
                }
            }

            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;
    }
};