Number of Substrings With Only 1s

Given a binary string s, return the number of substrings with all characters 1's. Since the answer may be too large, return it modulo 10<sup>9</sup> + 7.

Example 1:

Input: s = "0110111"
Output: 9
Explanation: There are 9 substring in total with only 1's characters.
"1" -> 5 times.
"11" -> 3 times.
"111" -> 1 time.

Example 2:

Input: s = "101"
Output: 2
Explanation: Substring "1" is shown 2 times in s.

Example 3:

Input: s = "111111"
Output: 21
Explanation: Each substring contains only 1's characters.

Constraints:

• 1 <= s.length <= 10<sup>5</sup>
• s[i] is either '0' or '1'.

## Problem Description

Given a binary string `s`, we need to find the number of substrings that contain only the character '1'. Since the answer can be large, we should return it modulo 10^9 + 7.

For example:

*   If `s = "0110111"`, the output is 9 because there are five "1" substrings, three "11" substrings, and one "111" substring.
*   If `s = "101"`, the output is 2 because there are two "1" substrings.
*   If `s = "111111"`, the output is 21 because there are six "1" substrings, five "11" substrings, four "111" substrings, three "1111" substrings, two "11111" substrings, and one "111111" substring.

## Brute Force Approach

A simple approach is to generate all possible substrings and count the ones that contain only '1's. This approach has a time complexity of O(n^2) because generating all substrings takes O(n^2) time, and checking each substring takes O(n) time in the worst case.

```python
def count_substrings_brute_force(s):
    n = len(s)
    count = 0
    for i in range(n):
        for j in range(i, n):
            substring = s[i:j+1]
            if all(c == '1' for c in substring):
                count += 1
    return count

Optimal Approach

A more efficient approach is to iterate through the string and count consecutive '1's. For each sequence of '1's, the number of substrings can be calculated using the formula n * (n + 1) / 2, where n is the length of the consecutive '1's. This is because a sequence of n '1's contains:

• n substrings of length 1
• n-1 substrings of length 2
• n-2 substrings of length 3
• ...
• 1 substring of length n

The sum of these substrings is n + (n-1) + (n-2) + ... + 1, which is equal to n * (n + 1) / 2.

def count_substrings(s):
    n = len(s)
    count = 0
    ones_count = 0
    
    for i in range(n):
        if s[i] == '1':
            ones_count += 1
        else:
            count += ones_count * (ones_count + 1) // 2
            ones_count = 0
            
    count += ones_count * (ones_count + 1) // 2
    return count % (10**9 + 7)

Big(O) Run-time Analysis

The optimal approach has a time complexity of O(n), where n is the length of the string. This is because we iterate through the string once to count consecutive '1's.

Big(O) Space Usage Analysis

The optimal approach has a space complexity of O(1) because we only use a few variables to store the count of '1's and the total count of substrings.

Edge Cases

• Empty String: If the input string is empty, the output should be 0.
• String with no 1s: If the input string contains only '0's, the output should be 0.
• String with only 1s: If the input string contains only '1's, the output should be n * (n + 1) / 2.
• Large output: The output should be modulo 10^9 + 7 to avoid integer overflow.