LC 3398. Smallest Substring With Identical Characters I

https://leetcode.com/problems/smallest-substring-with-identical-characters-i/description/

Tag: Binary Search

Hard: 2301

class Solution {
public:
    bool isValid(string &s, int target, int numOps) {
        int n = s.size();
        int l = 0, r = 0;
        int total = 0;
        while (r < n) {
            l = r;
            while (r < n && s[l] == s[r]) r++;
            int len = r - l;
            len -= target;
            int need = ceil(1.0 * len / (target + 1));
            total += need;
        }
        return total <= numOps;
    }
    int minLength(string s, int numOps) {
        int n = s.size();
        int need = 0;
        for (int i = 0; i < n; i++) {
            if (i % 2 && s[i] == '0') need += 1;
            else if (((i % 2) == 0) && s[i] == '1') need += 1;
        }
        if (need <= numOps) return 1;
        need = 0;
        for (int i = 0; i < n; i++) {
            if (i % 2 && s[i] == '1') need += 1;
            else if (((i % 2) == 0) && s[i] == '0') need += 1;
        }
        if (need <= numOps) return 1;
        int l = 2, r = n + 1;
        while (l < r) {
            int mid = (l + r) >> 1;
            if (isValid(s, mid, numOps)) r = mid;
            else l = mid + 1;
        }
        return l;
    }
};

本題基本上沒什麼特別的地方，我們可以透過二分搜來找到答案，並且我們可以對連續的相同 bit 進行分組，並且可以透過計算知道該組如果要符合長度為目標值得話需要多少次的操作，這樣計算一下就知道是否可以在限定的操作次數下達成目標。