Problem Statement in English

You’re given a binary string s (a string consisting only of ‘0’s and ‘1’s). A substring is a contiguous sequence of characters within the string.

Return the number of substrings that contain only ‘1’s. Since the answer may be very large, return it modulo $10^9 + 7$.

Approach

There is a formula for calculating the number of substrings in a string of length n: $n * (n + 1) / 2$.

Once we know this, all we need to do is just find the lengths of all contiguous segments of ‘1’s in the string s, and apply the formula to each segment. Finally, we sum up the results from all segments to get the total number of substrings containing only ‘1’s.

If you don’t know the formula, you can, through observation, realize that for every element in a subarray, each element provides those many more substrings. For example, a subarray of length one provides one substring, length two provides three substrings (the two individual elements and the combined one), length three provides six substrings (the three individual elements, the two-element combinations, and the full three-element combination), and so on.

Solution in Python


class Solution:
    def numSub(self, s: str) -> int:
        N = len(s)
        MOD = pow(10, 9) + 7
        zeros_indices = [-1]

        for i in range(len(s)):
            if s[i] == "0":
                zeros_indices.append(i)
        
        zeros_indices.append(N)
        
        res = 0

        for i in range(len(zeros_indices) - 1):
            l = zeros_indices[i]
            r = zeros_indices[i + 1]

            ones = r - l - 1
            res += ((ones * (ones + 1)) // 2) % MOD

        return res

Complexity

  • Time: $O(n)$
    Since we are iterating through the input string once.

  • Space: $O(n)$
    Since we are storing the indices of zeros in the input string.

And we are done.