3234. 統計 1 顯著的字符串的數量

思路

假設字串的長度為$n$，
$zero^2 \leq one \leq n$
$zero < \sqrt{n}$
也就是說，0 最多不會超過 $\sqrt{n}$ 個，
能透過這個資訊去降低原先 $O(n^2)$ 複雜度的解。

因此建立next數組，next[i + 1](記得是 + 1) 表示從位置 i 往後看，下一個 0 出現的位置，
用來讓指針j每次所在的位置，都會是0。

每次都先計算最佳情況，也就是 1 最多可以有幾個。
再算出可以刪去多少個 1，看有多少子字串滿足條件，加到答案中。

程式碼

枚舉

class Solution {
public:
    int numberOfSubstrings(string s) {
        int n = s.size();
        int lim = sqrt(n) + 1;
        // next[i + 1] 表示從位置 i 往後看，下一個 0 出現的位置
        int next[n + 1]; 
        next[n] = n;
        for(int i = n - 1; i >= 0; --i) {
            next[i] = next[i + 1];
            if(s[i] == '0') {
                next[i] = i;
            }
        }
        long long res = 0;
        for(int i = 0; i < n; ++i) { // 枚舉左端點
            int zero = s[i] == '0' ? 1 : 0;
            // zero 如果超出 sqrt(n)，那麼 one 不可能獲勝的
            for(int j = i; j < n && zero <= lim; j = next[j + 1], ++zero) {
                int one = (next[j + 1] - i) - zero; // 在尚未加入下一個零，最多 1 的狀態
                if(one >= 1LL * zero * zero) {
                    // 理論上能縮 step 這麼多
                    int step = one - zero * zero + 1;
                    // 實際上不能縮那麼多，最多就是這段的長度
                    res += min(step, next[j + 1] - j);
                }
            }
        }
        return res;
    }
};

複雜度分析

• 時間複雜度：$O(n\sqrt{n})$
• 空間複雜度：$O(n)$