Editorial

Solution walkthrough

Review the explanation, then compare the reference implementation.

Video explanation

Solution

Intuition

Every all-ones substring lies inside one maximal run of ones. A run of length r contributes 1 + 2 + ... + r = r*(r + 1)/2 substrings, since its successive positions end one, two, and then more valid substrings. Zeros separate independent runs.

Approach

Scan the string while counting consecutive ones. Python adds a completed run's triangular count when a zero appears and flushes the final run after the loop. JavaScript instead adds the current run length at each position, accumulating the same sum incrementally. Reset the run length at zeros and return the total modulo 10^9 + 7. Both variants count occurrences by position, not just distinct substring contents.

class Solution:
    def numSub(self, s: str) -> int:
        MOD = 10**9 + 7
        ones = 0
        res = 0

        # for x in s:
        #     if x == '1':
        #         ones += 1
        #         res = (res + ones) % MOD
        #     else:
        #         ones = 0
        # return res

        for x in s:
            if x == '1':
                ones += 1
            else:
                res += comb(ones + 1, 2) % MOD
                ones = 0
        
        if ones: res += comb(ones + 1, 2) % MOD
        return res % MOD

Complexity analysis

Both displayed solutions scan n = s.length characters once and perform constant work per character or completed run. Time is O(n) and auxiliary space is O(1).