Domain 2MediumMEDIUM

Number of Substrings With Only 1s

Count contiguous '1' substrings by summing run lengths modulo $10^9 + 7$.

Domain: String-Mathematics•Updated: 2026-09-17
#linear scan#string manipulation#O(N) time complexity#constant space

Problem Breakdown

We are given a binary string s containing only ‘0’ and ‘1’. The goal is to count every possible substring that consists entirely of the character ‘1’. Since we need substrings (contiguous sequences), any contiguous block of consecutive ‘1’s contributes multiple valid substrings.

Inputs: A single string s. Outputs: An integer representing the total count, modulo 109+710^9 + 7. Constraints: String length up to 10510^5, characters are strictly binary. Implicit Constraints/Edge Cases:

  • The result can exceed standard 32-bit integers (hence the modulo requirement).
  • A string of all ‘0’s should return 0.
  • We must handle large inputs efficiently (O(N)O(N) is required, O(N2)O(N^2) will Time Limit Exceed).

Intuition

A naive approach would be to iterate through every possible substring and check if it contains only ‘1’s. There are roughly N2/2N^2/2 substrings in a string of length NN. Checking each takes time proportional to its length, leading to an overall complexity around O(N3)O(N^3) or optimized to O(N2)O(N^2). Given the constraint N=105N=10^5, this is far too slow.

Key Insight: Substrings containing only ‘1’s are formed exclusively within contiguous segments of ‘1’s separated by ‘0’s’. A single ‘0’ breaks a sequence and resets our count for that segment.

Consider a contiguous block (run) of kk ones: ... 1, 1, ..., 1 ....

  • The last character contributes to the current run length as a new substring ending there.
  • If we have a run of length LL, it contains L(L+1)2\frac{L(L+1)}{2} substrings consisting only of ‘1’s (sum of integers from 1 to L).

Optimal Strategy: Instead of calculating the sum formula for each block, we can iterate through the string. Whenever we encounter a ‘1’, we increment our current run length counter and add that value directly to our total count. When we hit a ‘0’, we reset the run length counter to 0. This effectively calculates ∑i=1Li\sum_{i=1}^{L} i on the fly without needing separate arithmetic progression logic per block, keeping it simple and O(N)O(N).

Approach

  1. Initialize total_count = 0, current_run_length = 0. Define MOD = 10^9 + 7.
  2. Iterate through each character in string s:
    • If the character is ‘1’: Increment current_run_length by 1. Add this new length to total_count. Apply modulo at each addition (or just once before return, though intermediate application prevents overflow logic issues if ported).
    • If the character is ‘0’: Reset current_run_length to 0 because any substring crossing a ‘0’ contains non-‘1’s.
  3. Return total_count % MOD.

Complexity Analysis

  • Time Complexity: O(N)O(N), where NN is the length of string s. We traverse the input exactly once with constant-time operations inside the loop.
  • Space Complexity: O(1)O(1). We only use a few integer variables for counting and state tracking regardless of input size.

Solution

class Solution:
    def numSub(self, s: str) -> int:
        MOD = 10**9 + 7
        total_count = 0
        current_run_length = 0
        
        # Iterate through each character in the binary string
        for char in s:
            if char == '1':
                # Increment run length and add to total count.
                # Each new '1' extends all previous valid substrings ending at this position 
                # plus creates a new single-character substring of itself.
                current_run_length += 1
                total_count = (total_count + current_run_length) % MOD
            else:
                # Reset run length when encountering '0'.
                current_run_length = 0
                
        return total_count

Edge Cases Handled

  • All Zeros: The loop resets current_run_length every time, resulting in a final count of 0. Correct.
  • All Ones: current_run_length increments continuously; the sum accumulates correctly up to N(N+1)/2N(N+1)/2. Modulo ensures it fits requirements.
  • Single Character ‘1’: Loop runs once, adds 1 to total. Returns 1. Correct.
  • Large Input (10510^5): The linear scan handles this within time limits; modulo arithmetic prevents