#1513

Medium

LeetCode Problem Workspace

Number of Substrings With Only 1s

Calculate the number of contiguous substrings containing only 1s in a binary string using a math and string approach efficiently.

math string

Problem Statement

Given a binary string s, compute the total number of substrings that contain only the character '1'. Since the total may be large, return it modulo 10^9 + 7. Substrings are contiguous sequences of characters, and every group of consecutive 1s contributes to multiple valid substrings.

For example, if s = "0110111", the substrings consisting entirely of 1s are "1", "11", and "111" across different positions. Your task is to calculate the overall count for any binary string s within the given constraints.

Examples

Example 1

Input: s = "0110111"

Output: 9

There are 9 substring in total with only 1's characters. "1" -> 5 times. "11" -> 3 times. "111" -> 1 time.

Example 2

Input: s = "101"

Output: 2

Substring "1" is shown 2 times in s.

Example 3

Input: s = "111111"

Output: 21

Each substring contains only 1's characters.

Constraints

1 <= s.length <= 105
s[i] is either '0' or '1'.

Solution Approach

Iterate and Count Consecutive 1s

Traverse the string and maintain a counter for consecutive 1s. Reset the counter when encountering a 0 and compute the contribution of the previous segment immediately.

Compute Segment Contributions Using Math

For each segment of consecutive 1s of length n, the number of substrings is calculated as n*(n+1)/2. This uses the arithmetic series sum formula, efficiently converting the string pattern into a numeric contribution.

Aggregate and Apply Modulo

Sum all segment contributions during traversal and apply modulo 10^9 + 7 at each addition to prevent integer overflow. This ensures correctness for large strings while maintaining O(n) time complexity.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(n) because the string is traversed once. Space complexity is O(1) since only counters and the final sum are maintained, independent of string length.

What Interviewers Usually Probe

Check if the candidate recognizes the arithmetic series pattern in consecutive 1s.
Watch for correct handling of large results with modulo operations.
Assess whether the candidate optimizes by computing contributions in one pass instead of generating substrings.

Common Pitfalls or Variants

Common pitfalls

Attempting to generate all substrings explicitly, which causes timeouts for large strings.
Forgetting to reset the consecutive 1s counter after a 0, leading to incorrect sums.
Neglecting to apply modulo 10^9 + 7, risking overflow for long sequences of 1s.

Follow-up variants

Count substrings with only 0s instead of 1s, requiring minimal code adjustment.
Calculate substrings of exactly k consecutive 1s, modifying the arithmetic sum approach.
Extend to 3-character strings and count substrings where all characters are identical.

FAQ

What is the fastest way to count substrings with only 1s in a binary string?

Use a single pass to identify consecutive 1s segments, calculate each segment's substrings as n*(n+1)/2, and sum modulo 10^9+7.

Why do we use the formula n*(n+1)/2 for consecutive 1s?

It represents the sum of the first n positive integers, which directly counts all substrings in a segment of length n.

How does this approach handle very long strings?

By counting segment contributions on the fly and applying modulo arithmetic, the method avoids generating substrings and runs in O(n) time.

Can this method be adapted for counting 0-only substrings?

Yes, simply treat 0s as the consecutive character segments instead of 1s, keeping the arithmetic sum formula identical.

Which pattern does this problem exemplify for interview preparation?

It illustrates the Math plus String pattern, showing how string patterns translate into numeric series for efficient counting.

terminal

Solution

Solution 1: Traversal and Counting

We traverse the string $s$, using a variable $\textit{cur}$ to record the current count of consecutive 1s, and a variable $\textit{ans}$ to record the answer. When we traverse to character $s[i]$, if $s[i] = 0$, then set $\textit{cur}$ to 0; otherwise, increment $\textit{cur}$ by 1, then add $\textit{cur}$ to $\textit{ans}$, and take modulo $10^9 + 7$.

1

2

3

4

5

6

7

8

9

10

11

class Solution:
    def numSub(self, s: str) -> int:
        mod = 10**9 + 7
        ans = cur = 0
        for c in s:
            if c == "0":
                cur = 0
            else:
                cur += 1
                ans = (ans + cur) % mod
        return ans

Continue Practicing

#1573 number of ways to split a string #1447 simplified fractions #1360 number of days between two dates