Editorial

Solution walkthrough

Review the explanation, then compare the reference implementation.

Video explanation

Solution

Intuition

A substring with z zeros needs at least z^2 ones, so only about sqrt(n) zero counts can possibly work. For a fixed right endpoint, previous-zero links let us examine whole ranges of starting positions sharing the same zero count instead of testing every start.

Approach

Precompute prev[i], the last zero strictly before index i, or -1 if none exists. For each right endpoint i, start with j = i and the zero count of that final character.

In each iteration, starts from prev[j] + 1 through j all produce the current zero count. The earliest such start gives ones = (i - prev[j]) - zeros. Moving the start right within this range removes only ones, so the number of valid starts is min(j - prev[j], ones - zeros^2 + 1): the smaller of the range size and one plus the available surplus. Add this quantity only when the earliest start qualifies.

Jump j to prev[j] and increase the zero count. Stop when no earlier zero exists or zeros^2 > n. The start ranges are disjoint, so no substring is counted twice.

class Solution:
    def numberOfSubstrings(self, s: str) -> int:
        n = len(s)
        prev = [-1] * n # prev[i] = pos of last 0 to the left of i

        for i in range(1, n):
            if s[i - 1] == '0':
                prev[i] = i - 1
            else:
                prev[i] = prev[i - 1]

        res = 0
        for i in range(n):
            zeros = 1 if s[i] == '0' else 0
            j = i
            while j >= 0 and zeros**2 <= n:
                ones = (i - prev[j]) - zeros
                if ones >= zeros**2:
                    res += min(j - prev[j], ones - zeros**2 + 1) # min (curr unvisited range, surplus 1s in the entire range)
                j = prev[j]
                zeros += 1

        return res

Complexity analysis

Let n = s.length. Time: O(n * sqrt(n)). Auxiliary space: O(n) for previous-zero links.