LeetCode 1513 - Number of Substrings With Only 1s

Difficulty: 🟡 Medium
Topics: Math, String

Solution

Problem Understanding

The problem gives a binary string s, consisting only of the characters '0' and '1'. We must count how many substrings contain only '1' characters.

A substring is a contiguous section of the string. For example, in the string "111", the valid substrings made entirely of '1' are:

"1" at index 0
"1" at index 1
"1" at index 2
"11" from indices 0 to 1
"11" from indices 1 to 2
"111" from indices 0 to 2

This gives a total of 6 substrings.

The output should be the total number of such substrings, modulo 10^9 + 7. The modulo is necessary because the number of substrings can become very large when the string length approaches the maximum constraint.

The constraint 1 <= s.length <= 10^5 tells us that the input can be quite large. Any solution that examines all possible substrings directly will likely be too slow. Since a string of length n has O(n^2) substrings, we need a more efficient method.

Several edge cases are important:

A string containing only '0' characters should return 0.
A string containing only '1' characters should count every possible substring.
Alternating patterns like "101010" create many small valid groups.
Long consecutive runs of '1' characters can produce very large counts, so modular arithmetic is required.

Approaches

Brute Force Approach

The most straightforward solution is to generate every possible substring and check whether all characters inside it are '1'.

For every starting index i, we can try every ending index j, forming the substring s[i:j+1]. We then scan the substring to verify whether it contains only '1'.

This approach is correct because it explicitly examines every substring and counts exactly those that satisfy the condition.

However, it is too slow for the given constraints. There are O(n^2) substrings, and checking each substring can take up to O(n) time. This leads to a worst case complexity of O(n^3).

Even with optimizations, a substring enumeration approach still tends to be at least O(n^2), which is too slow for n = 10^5.

Optimal Approach

The key observation is that consecutive runs of '1' characters can be counted mathematically.

Suppose we encounter a block of consecutive '1' characters of length k.

For example:

"1" contributes 1 substring
"11" contributes 3 substrings
"111" contributes 6 substrings
"1111" contributes 10 substrings

The pattern is:

$$1 + 2 + 3 + \dots + k = \frac{k(k+1)}{2}$$

Instead of examining every substring individually, we only need to identify consecutive groups of '1' characters.

For each run of length k, we add:

$$\frac{k(k+1)}{2}$$

to the answer.

Since we scan the string only once, this gives an O(n) solution.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n³)	O(1)	Checks every substring individually
Optimal	O(n)	O(1)	Counts consecutive runs of `'1'` mathematically

Algorithm Walkthrough

Initialize a variable current_ones to track the current streak of consecutive '1' characters.
Initialize a variable total_substrings to store the final answer.
Traverse the string character by character.
If the current character is '1', increment current_ones because the streak continues.
Every time we extend a streak of '1', we gain additional valid substrings ending at the current position. Specifically, if the streak length becomes k, then exactly k valid substrings end at this position.
Add current_ones to total_substrings.
If the current character is '0', reset current_ones to 0 because the streak is broken.
Apply modulo 10^9 + 7 during accumulation to prevent overflow.
After processing the entire string, return the result.

Why it works

At every position, current_ones represents the number of consecutive '1' characters ending at that index.

If the streak length is k, then there are exactly k substrings ending at this position that contain only '1':

The last character alone
The last two characters
The last three characters
...
The entire streak

By adding current_ones at every step, we count every valid substring exactly once.

Python Solution

class Solution:
    def numSub(self, s: str) -> int:
        MOD = 10**9 + 7

        current_ones = 0
        total_substrings = 0

        for char in s:
            if char == '1':
                current_ones += 1
                total_substrings += current_ones
            else:
                current_ones = 0

            total_substrings %= MOD

        return total_substrings

The implementation maintains two running variables.

current_ones stores the length of the current consecutive sequence of '1' characters. Whenever a '1' is encountered, the streak grows by one.

The crucial insight is that a streak of length k contributes exactly k new substrings ending at the current index. Therefore, we immediately add current_ones to the total.

When a '0' appears, the streak is broken, so current_ones resets to 0.

The modulo operation is applied during accumulation to keep the value within bounds.

Go Solution

func numSub(s string) int {
    const MOD int = 1000000007

    currentOnes := 0
    totalSubstrings := 0

    for _, char := range s {
        if char == '1' {
            currentOnes++
            totalSubstrings += currentOnes
        } else {
            currentOnes = 0
        }

        totalSubstrings %= MOD
    }

    return totalSubstrings
}

The Go implementation follows the same logic as the Python version.

Go uses explicit integer declarations, and the modulo constant is defined as an integer constant. Since the result can grow large, applying modulo during accumulation prevents overflow issues.

The loop iterates through characters using Go's range syntax over the string.

Worked Examples

Example 1

Input:

s = "0110111"

Index	Character	current_ones	Added to Total	total_substrings
0	0	0	0	0
1	1	1	1	1
2	1	2	2	3
3	0	0	0	3
4	1	1	1	4
5	1	2	2	6
6	1	3	3	9

Final answer:

Example 2

Input:

s = "101"

Index	Character	current_ones	Added to Total	total_substrings
0	1	1	1	1
1	0	0	0	1
2	1	1	1	2

Final answer:

Example 3

Input:

s = "111111"

Index	Character	current_ones	Added to Total	total_substrings
0	1	1	1	1
1	1	2	2	3
2	1	3	3	6
3	1	4	4	10
4	1	5	5	15
5	1	6	6	21

Final answer:

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	The string is scanned exactly once
Space	O(1)	Only a few integer variables are used

The algorithm performs a single linear pass through the string. Each character is processed once, and all operations inside the loop take constant time.

No additional data structures proportional to the input size are required, so the space complexity remains constant.

Test Cases

solution = Solution()

assert solution.numSub("0110111") == 9      # Example case with multiple groups
assert solution.numSub("101") == 2          # Alternating pattern
assert solution.numSub("111111") == 21      # Entire string is ones

assert solution.numSub("0") == 0            # Single zero
assert solution.numSub("1") == 1            # Single one

assert solution.numSub("00000") == 0        # All zeros
assert solution.numSub("11111") == 15       # All ones

assert solution.numSub("1010101") == 4      # Multiple isolated ones
assert solution.numSub("110011") == 6       # Two separate groups

assert solution.numSub("100001") == 2       # Ones separated by many zeros
assert solution.numSub("1110111") == 12     # Two equal-sized groups

assert solution.numSub("1111011111") == 25  # Uneven groups of ones

large_input = "1" * 100000
expected = (100000 * 100001 // 2) % (10**9 + 7)
assert solution.numSub(large_input) == expected  # Maximum size stress test

Test Summary

Test	Why
`"0110111"`	Verifies multiple groups of ones
`"101"`	Tests isolated single ones
`"111111"`	Tests continuous run of ones
`"0"`	Minimum input with no valid substring
`"1"`	Minimum input with one valid substring
`"00000"`	Ensures zeros reset streak correctly
`"11111"`	Validates arithmetic growth of counts
`"1010101"`	Tests repeated streak resets
`"110011"`	Verifies independent counting of groups
`"100001"`	Handles long zero gaps
`"1110111"`	Tests multiple equal runs
`"1111011111"`	Tests uneven consecutive groups
Large all-ones input	Confirms scalability and modulo handling

Edge Cases

One important edge case is a string containing only zeros, such as "00000". A buggy implementation might accidentally count empty substrings or fail to reset the running streak correctly. In this implementation, every '0' immediately resets current_ones to 0, ensuring no invalid substrings are counted.

Another critical case is a string containing only ones, such as "111111". This creates the maximum number of valid substrings for a given length. The implementation correctly accumulates the arithmetic progression 1 + 2 + 3 + ... + n, which equals n(n+1)/2.

A third important edge case is alternating characters like "101010". Here, every valid substring has length 1. Some implementations incorrectly merge separated streaks of ones. This solution avoids that issue because the streak counter resets immediately whenever a '0' is encountered.

A final important case is the maximum input size, especially when the string consists entirely of ones. The number of substrings becomes extremely large, so failing to apply modulo arithmetic could lead to overflow in some languages. The implementation applies modulo during accumulation, ensuring correctness even for the largest allowed input.