algorithm - 1 と 0 のみを含む文字列を指定すると、1 が 0 より大きい部分文字列の数を返します

Question

S が 0 と 1 のみを含む文字列であるとします。0 の数が 1 の数よりも少ない、S の null でない部分文字列の数を数えたいと思います。

以下に示す総当り法を使用して、この問題を O(n^2) で解決するアルゴリズムを作成できます。

moreOnes(s):
count = 0
n = s.len()

for i = 1 to n
    one = 0
    zero = 0
    for j = i to n
        if s[i] == '1'
            one++
        else
            zero++
        
        if one > zero
            count++

return count

しかし、時間の複雑さが O(n*logn) または O(n) で、空間の複雑さが O(1) から O(n) のいずれかであるアルゴリズムを使用できるでしょうか?