Number of Substrings With Only 1s: Counting Consecutive Groups

Given a binary string s (a string containing only '0' and '1'), return the number of substrings that consist entirely of '1' characters. Since the answer may be very large, return it modulo 10^9 + 7.

This is LeetCode 1513: Number of Substrings With Only 1s, and it is an excellent problem for learning how to count substrings efficiently using a running tally instead of brute-force enumeration.

Why this problem matters

Counting substrings is one of the most common patterns in string problems. The brute-force approach (check every possible substring) takes O(n^2) time, which is too slow for large inputs. This problem teaches you a cleaner technique: instead of enumerating every substring, you track consecutive runs and use simple math to compute the count in O(n) time.

The same "count consecutive groups" idea shows up in problems involving runs of characters, binary array analysis, and any scenario where you need to tally contiguous segments efficiently.

The key insight

Every group of consecutive 1s of length k contributes exactly k * (k + 1) / 2 substrings. Why? A group like "111" (k = 3) contains:

• Three substrings of length 1: "1", "1", "1"
• Two substrings of length 2: "11", "11"
• One substring of length 3: "111"

That is 3 + 2 + 1 = 6 = 3 * 4 / 2.

But you do not even need to find the groups explicitly. You can compute this on the fly: as you scan the string, keep a counter of how many consecutive 1s you have seen so far. Each time you see a '1', increment the counter and add its current value to the result. When you see a '0', reset the counter to zero.

Why does this work? When the counter is k, it means you just extended the current group to length k. The new character contributes exactly k new substrings (all the substrings that end at the current position). Over the course of the entire group, you add 1 + 2 + 3 + ... + k = k * (k + 1) / 2, which is exactly the formula.

The solution

def num_sub(s: str) -> int:
    MOD = 10**9 + 7
    result = 0
    consecutive = 0

    for ch in s:
        if ch == "1":
            consecutive += 1
            result = (result + consecutive) % MOD
        else:
            consecutive = 0

    return result

Let's walk through what each piece does.

The variable consecutive tracks the length of the current run of 1s. Every time we encounter a '1', we increment it and add the new value to result. This works because the k-th 1 in a group creates k new substrings (all substrings ending at that position within the group).

When we encounter a '0', we reset consecutive to zero. The current group is over, and any future 1s belong to a new group.

The modulo operation % MOD keeps the result within bounds, since the problem specifies that the answer could be very large.

Visual walkthrough

Let's trace through the string "0110111" character by character. Watch how consecutive resets at each '0' and accumulates at each '1', with result growing by the current consecutive value at every step.

Notice that the counter-based approach produces the same totals as the group formula. The first group of two 1s adds 1 + 2 = 3. The second group of three 1s adds 1 + 2 + 3 = 6. The final result is 9.

Complexity analysis

Time is O(n) where n is the length of the string. We scan each character exactly once and do constant work per character: one comparison, one addition, and one modulo operation.

Space is O(1). We only store two integer variables (consecutive and result), regardless of the input size. No arrays, no hash maps, no auxiliary data structures.

The building blocks

1. Counting substrings that end at position i

The core pattern: when you extend a run of matching characters by one, the number of new substrings is equal to the current run length.

consecutive = 0
for ch in s:
    if ch == target:
        consecutive += 1
        count += consecutive
    else:
        consecutive = 0

This pattern applies to any problem where you count contiguous substrings of a single repeated character. You will see it in "Count Number of Homogenous Substrings" (LeetCode 1759) and similar problems. The key realization is that each new character in the run creates substrings of every possible length ending at that character.

2. Modular arithmetic for large counts

When a problem says "return the answer modulo 10^9 + 7," apply the modulo at every addition, not just at the end.

MOD = 10**9 + 7
result = (result + value) % MOD

Taking the modulo at each step prevents integer overflow in languages with fixed-width integers and keeps the arithmetic correct. In Python, integers can grow arbitrarily large, but applying modulo incrementally is still good practice because it matches what you would do in C++ or Java, and interviewers expect to see it.

Edge cases

Before submitting, think through these scenarios:

• All zeros: "0000". No 1s exist, so the answer is 0. The counter never increments.
• All ones: "1111" (length n). The answer is n * (n + 1) / 2. For n = 4, that is 10.
• Single character: "1" returns 1. "0" returns 0.
• Alternating: "10101". Each 1 is isolated, so each contributes 1 substring. Answer equals the count of 1s.
• Very long string of all ones: n = 100,000. The raw count is roughly 5 * 10^9, which exceeds 10^9 + 7. The modulo is essential here.
• Empty string: not possible per the constraints (length is at least 1), but consecutive = 0 and result = 0 would handle it correctly.

From understanding to recall

You have seen how counting consecutive 1s and adding the running counter produces the correct count of all-1 substrings in a single pass. The logic is short and the math is clean. But reproducing it under pressure requires remembering the exact pattern: increment and add when you see a 1, reset when you see a 0, modulo at every step.

The details that trip people up are small but costly. Do you add consecutive before or after incrementing? Do you apply modulo to each addition or only at the end? Do you reset to 0 or to 1? These are not conceptual errors. They are recall gaps, and they cost time in interviews.

Spaced repetition closes these gaps. You practice writing the consecutive counter loop from memory, then the modular addition, then the reset logic. After a few rounds, the pattern is automatic. You see "count substrings of a single character" in a problem, and the solution flows out without hesitation.

Related posts

• Add Binary - Another problem that processes binary strings character by character with a running accumulator
• Decode Ways - Counting valid groupings in a string using dynamic programming, a more complex version of substring counting
• Count and Say - Builds strings by counting consecutive runs of characters, the same "group consecutive elements" idea

CodeBricks breaks Number of Substrings With Only 1s into its consecutive counting and modular arithmetic building blocks, then drills them independently with spaced repetition. You type each piece from scratch until the pattern is automatic. When a string counting problem shows up in your interview, you do not think about it. You just write it.