LeetCode Challenge Day 61 — 3234. Count the Number of Substrings With Dominant Ones

Hey folks 👋

This is Day 61 of my LeetCode streak 🚀
Today’s problem is 3234 — Count the Number of Substrings With Dominant Ones.

A substring is said to have dominant ones if:

(# of 1s) ≥ (# of 0s)²

That squared term makes the problem interesting — and immediately tells us brute force won't work.

📌 Problem Overview

Given a binary string s, return the number of substrings where:

• ones >= zeros²

Example:
For "00011" → Output: 5

💡 Intuition

We split the problem into two cases:

1️⃣ Case k = 0 zeros (all-ones substrings)

Every substring made purely of 1s automatically satisfies:

ones >= 0²

So we count all runs of consecutive 1s:

A run of length L contributes:

L × (L + 1) / 2

2️⃣ Case k ≥ 1 zeros

More interesting part.

For a substring with exactly k zeros, the condition becomes:

#ones ≥ k²

Let’s observe:

• If k becomes too large (e.g., 100), k² becomes 10,000
• Since n ≤ 4 × 10⁴, meaningful k values are only up to √n ≈ 200

So we only enumerate k = 1..√n.

For each k, we:

• Take all windows of k consecutive zeros in the string
• Compute:
  • base ones inside this window
  • how many ones we can extend left/right

This becomes a 2-D counting problem:

count pairs (x, y) such that x + y ≥ need

Where:

• x = how many ones taken left
• y = how many ones taken right
• need = k² - baseOnes

We compute the number of valid (x, y) pairs using a fast arithmetic method.

This avoids brute force and gives an efficient solution.

🔑 Approach Summary

✔ Count all-ones substrings
✔ Extract zero positions
✔ For every k from 1 to √n:

• Slide a window of k zeros
• Compute left/right extension limits
• Count valid (x, y) pairs using math
• Add to answer

Total complexity:
O(n × √n) — easily fast for constraints.

🧑‍💻 Code (JavaScript)

/**
 * @param {string} s
 * @return {number}
 */
var numberOfSubstrings = function(s) {
    const n = s.length;
    const zeroPos = [];
    for (let i = 0; i < n; ++i) if (s[i] === '0') zeroPos.push(i);
    const m = zeroPos.length;
    let ans = 0;

    // 1) Count all-ones substrings
    let i = 0;
    while (i < n) {
        if (s[i] === '1') {
            let j = i;
            while (j + 1 < n && s[j + 1] === '1') j++;
            const L = j - i + 1;
            ans += L * (L + 1) / 2;
            i = j + 1;
        } else i++;
    }
    if (m === 0) return ans;

    // Pair counting helper
    function countPairsLE(L, R, t) {
        if (t < 0) return 0;
        const maxT = L + R - 2;
        if (t >= maxT) return L * R;

        const up = Math.min(L - 1, t);
        const split = t - R + 1;
        const a = Math.min(up, split);
        let res = 0;
        if (a >= 0) res += (a + 1) * R;

        const start = Math.max(a + 1, 0);
        if (start <= up) {
            const cnt = up - start + 1;
            const first = t - start + 1;
            const last = t - up + 1;
            res += (first + last) * cnt / 2;
        }
        return res;
    }

    // Limit k to sqrt(n)
    const K = Math.floor(Math.sqrt(n)) + 1;

    // 2) Count substrings with k zeros
    for (let k = 1; k <= K; ++k) {
        if (k > m) break;
        for (let startIdx = 0; startIdx + k - 1 < m; ++startIdx) {
            const endIdx = startIdx + k - 1;

            const prevZero = (startIdx === 0) ? -1 : zeroPos[startIdx - 1];
            const nextZero = (endIdx + 1 === m) ? n : zeroPos[endIdx + 1];

            const L = zeroPos[startIdx] - prevZero;
            const R = nextZero - zeroPos[endIdx];

            const windowLen = zeroPos[endIdx] - zeroPos[startIdx] + 1;
            const baseOnes = windowLen - k;

            const need = k * k - baseOnes;
            if (need <= 0) {
                ans += L * R;
            } else {
                const totalPairs = L * R;
                const bad = countPairsLE(L, R, need - 1);
                ans += totalPairs - bad;
            }
        }
    }

    return ans;
};

🎯 Example Walkthrough

Consider:

s = "00011"

Dominant substrings include:

• "1"

• "1"

• "01"

• "11"

• "011"

Total: 5

🧠 Reflection

This problem is a great example of how:

• squaring conditions (k²) limit search space

• structural decomposition (run-lengths, zero windows)

• math-based counting
  can combine for a powerful optimization.

These techniques show up frequently in medium/hard string problems — definitely worth mastering.

See you tomorrow for Day 62! 🚀
Happy Coding 👨‍💻✨