Start by iterating through the string and counting consecutive 1s segments. Each segment of length n contributes n*(n+1)/2 substrings to the total count. Sum contributions from all segments and return the result modulo 10^9+7 to handle large outputs.
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.
How GhostInterview Helps
- Automatically identifies consecutive 1s segments and computes contributions without manual substring enumeration.
- Ensures correct modulo arithmetic is applied, preventing overflow in large input cases.
- Provides step-by-step breakdown of segment math, illustrating the Math plus String pattern central to this problem.
Topic Pages
Related GhostInterview Pages
- LeetCode Interview Copilot - Use GhostInterview as a live solver when you want direct help with LeetCode-style coding questions.
- Coding Interview Assistant - See how GhostInterview supports array, string, linked list, graph, and tree interview workflows.
- How GhostInterview Works - Review the screenshot, reasoning, and answer flow before using the solver in a live interview.
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.
Need direct help with Number of Substrings With Only 1s instead of spending more time grinding it?
Download GhostInterview when you want a LeetCode solver, not another long practice loop. Capture Number of Substrings With Only 1s from a screenshot, get the answer path and complexity, and use supported stealth workflows that stay outside captured layers.
Capture the prompt fast instead of rewriting the problem by hand.
Get the solution path, trade-offs, and complexity summary in one pass.
Stay outside captured layers on supported screen-share workflows.
Stay in the same pattern family
Count the number of ways to split a binary string into three non-empty parts with equal numbers of '1's.
Open problem page#1447 Simplified FractionsGenerate simplified fractions between 0 and 1 with denominators up to a given integer n.
Open problem page#1360 Number of Days Between Two DatesCalculate the exact number of days between two dates using string parsing and arithmetic logic with consistent accuracy.
Open problem page