最长合法子串长度

[题目链接](https://www.nowcoder.com/practice/bda1d9a196644a66a233ab91144b41d4)

思路

给定一个 01 字符串，每次操作可以将一个 '1' 变成 '0'，最多执行 $k$ 次操作。要求最小化操作后最长全 1 子串的长度。

"最小化最大值" 是经典的二分答案模型。

二分答案

二分目标值 $\textit{mid}$ ，表示"操作后最长全 1 子串长度不超过 $\textit{mid}$ "，然后贪心判断是否可行。

贪心判定

先预处理出所有极长全 1 段的长度。对于一段长度为 $L$ 的全 1 段，我们要在其中放置若干个 '0'（即执行若干次操作），使得每一段剩余的全 1 子串长度不超过 $\textit{mid}$ 。

关键观察：每次操作将一个 '1' 变为 '0'，这个 '0' 本身占据一个位置，所以它既"切割"了连续段，又"消耗"了一个长度。

设需要 $c$ 次操作，则：

产生 $c+1$ 段全 1 子串；
总长度为 $L - c$ （因为 $c$ 个位置变成了 '0'）；
最优策略是均匀切割，使最长段长度为 $\lceil \frac{L-c}{c+1} \rceil$ 。

要满足 $\lceil \frac{L-c}{c+1} \rceil \le \textit{mid}$ ，等价于 $L - c \le \textit{mid} \cdot (c+1)$ ，即：

$ $c \ge \frac{L - \textit{mid}}{\textit{mid} + 1}$ $

所以对长度为 $L$ 的段，所需操作次数为：

$ $c = \max\!\left(0,\; \left\lceil \frac{L - \textit{mid}}{\textit{mid} + 1} \right\rceil\right)$ $

将所有段所需的操作次数求和，若总和 $\le k$ ，则 $\textit{mid}$ 可行。

二分范围

下界： $0$ （把所有 '1' 全变成 '0'）；
上界：最长全 1 段的长度（不做任何操作）。

样例演示

字符串 "101110110"， $k=1$ 。

全 1 段长度为 $[1, 3, 2]$ 。

尝试 $\textit{mid}=2$ ：段长 1 需要 $0$ 次，段长 3 需要 $\lceil\frac{3-2}{3}\rceil = 1$ 次，段长 2 需要 $0$ 次，共 $1 \le k$ ，可行。
尝试 $\textit{mid}=1$ ：段长 1 需要 $0$ 次，段长 3 需要 $\lceil\frac{3-1}{2}\rceil = 1$ 次，段长 2 需要 $\lceil\frac{2-1}{2}\rceil = 1$ 次，共 $2 > k$ ，不可行。

答案为 $2$ 。

复杂度

时间复杂度： $O(n \log n)$ ，其中 $n$ 为字符串长度。二分次数 $O(\log n)$ ，每次判定扫描所有段 $O(n)$ 。
空间复杂度： $O(n)$ ，存储所有全 1 段的长度。

代码

C++
Java

class Solution {
public:
    int maxLen(string s, int k) {
        vector<int> segs;
        int n = s.size();
        int i = 0;
        while (i < n) {
            if (s[i] == '1') {
                int j = i;
                while (j < n && s[j] == '1') j++;
                segs.push_back(j - i);
                i = j;
            } else {
                i++;
            }
        }
        if (segs.empty()) return 0;

        int lo = 0, hi = *max_element(segs.begin(), segs.end());
        while (lo < hi) {
            int mid = (lo + hi) / 2;
            long long ops = 0;
            for (int len : segs) {
                if (len > mid) {
                    if (mid == 0) {
                        ops += len;
                    } else {
                        long long need = (long long)len - mid;
                        long long div = (long long)mid + 1;
                        ops += (need + div - 1) / div;
                    }
                }
            }
            if (ops <= k) hi = mid;
            else lo = mid + 1;
        }
        return lo;
    }
};

import java.util.*;

public class Solution {
    public int maxLen (String s, int k) {
        List<Integer> segs = new ArrayList<>();
        int n = s.length();
        int i = 0;
        while (i < n) {
            if (s.charAt(i) == '1') {
                int j = i;
                while (j < n && s.charAt(j) == '1') j++;
                segs.add(j - i);
                i = j;
            } else {
                i++;
            }
        }
        if (segs.isEmpty()) return 0;

        int lo = 0, hi = 0;
        for (int len : segs) hi = Math.max(hi, len);

        while (lo < hi) {
            int mid = (lo + hi) / 2;
            long ops = 0;
            for (int len : segs) {
                if (len > mid) {
                    if (mid == 0) {
                        ops += len;
                    } else {
                        long need = (long) len - mid;
                        long div = (long) mid + 1;
                        ops += (need + div - 1) / div;
                    }
                }
            }
            if (ops <= k) hi = mid;
            else lo = mid + 1;
        }
        return lo;
    }
}