Number of Substrings With Only 1s: Counting Consecutive Groups

LeetCode 1513, Number of Substrings With Only 1s, asks you to count how many substrings of a binary string consist entirely of 1s. Since the answer can be very large, you return it modulo 10^9 + 7.

At first you might think about generating every substring and checking if it contains only 1s, but that would be O(n^2). There is a clean O(n) solution once you spot the mathematical pattern hiding in consecutive runs of 1s.

The problem

Given a binary string s, return the number of substrings where every character is '1'. Return the result modulo 10^9 + 7.

Example 1: s = "0110111" returns 9. The substrings with only 1s are "1" (occurring 5 times at different positions), "11" (occurring 3 times), and "111" (occurring once). That gives 5 + 3 + 1 = 9.

Example 2: s = "101" returns 2. Each '1' contributes one substring.

Example 3: s = "111111" returns 21. A group of 6 consecutive 1s produces 6 + 5 + 4 + 3 + 2 + 1 = 21 substrings.

The approach

The key insight is that you do not need to examine every substring. Instead, think about what happens when you scan left to right and track how many consecutive 1s you have seen so far.

Every time you encounter a '1', you extend the current run by one. A run of length k ending at the current position contributes exactly k new substrings, because you can start a substring at any of the k positions in the run and end it at the current position.

Here is the logic:

1. Maintain a counter consecutive that tracks how many 1s in a row you have seen.
2. When you see a '1', increment consecutive and add its value to result.
3. When you see a '0', reset consecutive to 0.
4. Return result % (10^9 + 7).

Why does adding consecutive at each step give the right count? Consider a group of three 1s at positions 4, 5, 6. At position 4, consecutive = 1 and you add 1 (the substring "1" starting and ending at 4). At position 5, consecutive = 2 and you add 2 (the substrings "1" at position 5 and "11" spanning positions 4 to 5). At position 6, consecutive = 3 and you add 3 (the substrings "1", "11", "111"). Total for this group: 1 + 2 + 3 = 6, which equals k*(k+1)/2 for k = 3.

The code

def numSub(s):
    MOD = 10**9 + 7
    result = 0
    consecutive = 0

    for ch in s:
        if ch == "1":
            consecutive += 1
            result += consecutive
        else:
            consecutive = 0

    return result % MOD

consecutive = 0. This tracks the length of the current run of 1s. It resets to 0 whenever you see a '0'.

if ch == "1". When the character is '1', you extend the run. The current run of length consecutive contributes consecutive new substrings that all end at this position.

result += consecutive. Each new '1' at position i creates substrings starting at every position within the current run and ending at i. That is exactly consecutive new substrings.

consecutive = 0. When you hit a '0', the run breaks. No substrings of only 1s can include this position, so you reset.

return result % MOD. The problem requires the answer modulo 10^9 + 7. You can also apply the modulo inside the loop with result = (result + consecutive) % MOD for safety with very long strings.

Visual walkthrough

Here is a step-by-step trace on the string "0110111". Watch how consecutive grows within each group of 1s and resets at each 0.

The algorithm scans left to right in a single pass. Each '1' adds the current streak length to the result. Each '0' resets the streak. The final result of 9 matches the sum of substrings from the two groups: 3 from the group of two 1s and 6 from the group of three 1s.

Complexity analysis

Both the group formula and running counter approaches are optimal. The running counter is slightly simpler to code because you do not need to explicitly detect where groups begin and end.

Building blocks

Consecutive counting

The pattern of tracking a running count of identical consecutive elements is one of the most reusable building blocks in string and array problems. You maintain a counter that grows when the condition holds and resets when it breaks. This same loop structure appears in Consecutive Characters (tracking the longest streak), Count Binary Substrings (comparing adjacent group sizes), and any run-length encoding problem. Once you own this building block, you snap it into new problems without thinking about the loop mechanics.

Triangular number formula

A group of k consecutive 1s produces k*(k+1)/2 substrings. This is the triangular number formula. You do not need to memorize it as a separate fact, because the running counter approach derives it incrementally: 1 + 2 + 3 + ... + k = k*(k+1)/2. But recognizing that a "count all sub-runs" question maps to triangular numbers helps you verify your answer quickly and connects this problem to a broader family of counting problems.

Edge cases

• All zeros. A string like "0000" has no 1s at all. consecutive never increments, so the result is 0.
• All ones. A string like "1111" is one big group. The answer is k*(k+1)/2 = 4*5/2 = 10.
• Single character. "1" returns 1. "0" returns 0.
• Alternating. A string like "10101" has three isolated 1s. Each contributes 1, so the answer is 3.
• Very long strings. With s up to 10^5 characters of all 1s, the raw sum reaches about 5 * 10^9, which fits in a 64-bit integer. The modulo operation at the end (or inside the loop) keeps the result in range.
• Modulo matters. If s has 100,000 ones in a row, the answer is 5,000,050,000 before modulo. Forgetting the % MOD step is a common mistake.

From understanding to recall

The logic here is short, just a counter and an accumulator, but the details matter. Do you reset consecutive to 0 or to 1 when you see a '0'? Do you add consecutive before or after incrementing? Do you apply the modulo at the end or inside the loop?

These are exactly the kinds of micro-decisions that slip under pressure. Practice writing the solution from scratch on a blank screen. The entire function is six lines. Once you can write it without pausing, space out your reviews and let spaced repetition lock in the pattern. The consecutive-counting brick will serve you in many other problems.

Related posts

• Consecutive Characters - The same streak-counting pattern applied to finding the longest run
• Count Binary Substrings - Another binary string problem using group counting at boundaries
• Number of 1 Bits - Counting 1s in binary representations with bit manipulation