Problem Description

You are given a binary string s (a string consisting only of the characters '0' and '1'). Your task is to count the number of substrings in s that contain only the character '1'.

A substring is a contiguous sequence of characters within the string. For example, in s = "0110111", the substrings "1", "11", and "111" are all valid substrings consisting only of '1's.

• Each substring must contain at least one character.
• Substrings must be contiguous (no skipping characters).
• The answer can be large, so return it modulo 10^9 + 7.

Constraints:

• 1 <= s.length <= 10^5
• s consists only of '0' and '1'

Thought Process

At first glance, you might think about checking every possible substring of s to see if it contains only '1's, then count it if it does. However, this brute-force approach would require checking O(n²) substrings, which is not feasible for large strings.

To optimize, notice that all valid substrings must be made up of consecutive '1's. That means we can focus on runs (groups) of consecutive '1's. For each such run, we can count how many substrings can be formed using just those '1's.

The key insight is: for a run of k consecutive '1's, there are k * (k + 1) / 2 substrings consisting only of '1's (think of all substrings starting and ending within this run).

Solution Approach

• Initialize a variable to keep track of the total count of valid substrings.
• Iterate through the string, keeping a counter for the current run of consecutive '1's.
• When you encounter a '1', increment the counter.
• When you encounter a '0' or reach the end of the string, compute the number of substrings for the current run of '1's using the formula k * (k + 1) / 2 and add it to the total. Then reset the counter.
• At the end, return the total count modulo 10^9 + 7.

This approach is efficient because it processes the string in a single pass and does constant work for each character.

Example Walkthrough

Let's use s = "0110111" as an example:

• Index 0: '0' — no run of '1's yet.
• Index 1: '1' — start a run (count = 1).
• Index 2: '1' — continue run (count = 2).
• Index 3: '0' — run ends. Number of substrings: 2 * 3 / 2 = 3. Add to total (total = 3). Reset count.
• Index 4: '1' — start new run (count = 1).
• Index 5: '1' — continue run (count = 2).
• Index 6: '1' — continue run (count = 3).
• End of string: run ends. Number of substrings: 3 * 4 / 2 = 6. Add to total (total = 9).

So, the answer for "0110111" is 9.

Time and Space Complexity

• Brute-force approach: O(n²) time and O(1) space. This is because there are O(n²) substrings in a string of length n, and checking each substring for only '1's takes O(n) time in total.
• Optimized approach: O(n) time and O(1) space. We only scan the string once, and use a few variables to keep track of counts. This is much more efficient and works for large inputs.

Summary

The elegant solution to this problem leverages the observation that all substrings of only '1's are contained within runs of consecutive '1's. By counting the length of each such run and applying the formula for the number of substrings in a sequence, we can efficiently compute the total number of valid substrings in a single pass. This approach is both fast and easy to implement, making it ideal for large input sizes.

Code Implementation

class Solution:
    def numSub(self, s: str) -> int:
        MOD = 10 ** 9 + 7
        count = 0
        total = 0
        for c in s:
            if c == '1':
                count += 1
            else:
                total += count * (count + 1) // 2
                count = 0
        # Add the last run if the string ends with '1'
        total += count * (count + 1) // 2
        return total % MOD
      

class Solution {
public:
    int numSub(string s) {
        const int MOD = 1e9 + 7;
        long long count = 0, total = 0;
        for (char c : s) {
            if (c == '1') {
                count++;
            } else {
                total += count * (count + 1) / 2;
                count = 0;
            }
        }
        total += count * (count + 1) / 2;
        return total % MOD;
    }
};
      

class Solution {
    public int numSub(String s) {
        final int MOD = 1000000007;
        long count = 0, total = 0;
        for (char c : s.toCharArray()) {
            if (c == '1') {
                count++;
            } else {
                total += count * (count + 1) / 2;
                count = 0;
            }
        }
        total += count * (count + 1) / 2;
        return (int)(total % MOD);
    }
}
      

var numSub = function(s) {
    const MOD = 1e9 + 7;
    let count = 0, total = 0;
    for (let c of s) {
        if (c === '1') {
            count++;
        } else {
            total += count * (count + 1) / 2;
            count = 0;
        }
    }
    total += count * (count + 1) / 2;
    return total % MOD;
};