Given a binary string s, return the number of substrings with all characters 1's. Since the answer may be too large, return it modulo 109 + 7.
Example 1:
Input: s = "0110111" Output: 9 Explanation: 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 Explanation: Substring "1" is shown 2 times in s.
Example 3:
Input: s = "111111" Output: 21 Explanation: Each substring contains only 1's characters.
Constraints:
1 <= s.length <= 105s[i] is either '0' or '1'.Problem Overview: Given a binary string s, count how many substrings contain only the character '1'. Every contiguous block of ones contributes multiple valid substrings, so the task reduces to efficiently counting substrings formed inside these blocks.
Approach 1: Brute Force Substring Check (O(n^2) time, O(1) space)
Generate every possible substring and check whether it contains only '1'. Use two nested loops: the outer loop selects the start index and the inner loop extends the substring while characters remain '1'. Each time the extension still contains only ones, increment the count. The moment a '0' appears, stop extending that start index. This approach works but still explores up to O(n^2) substrings in the worst case (for example, a string of all ones), which becomes too slow for large inputs.
Approach 2: Consecutive Ones Counting and Arithmetic (O(n) time, O(1) space)
The key observation: if you have a consecutive run of k ones, the number of substrings made entirely of ones inside that run is k * (k + 1) / 2. For example, the block "111" produces substrings "1", "1", "1", "11", "11", and "111" — six total. Instead of checking substrings explicitly, iterate through the string once and maintain a counter for the current streak of consecutive ones. Each time you see '1', increase the streak and add it to the answer. When you encounter '0', reset the streak to zero.
This works because every new '1' extends all previous valid substrings ending at the previous index and also forms a new substring by itself. The algorithm performs a single pass through the string and uses constant memory. Since the result can be large, apply modulo 1e9 + 7. The reasoning relies on simple combinatorics from math and sequential processing of the string.
Recommended for interviews: The consecutive ones counting approach is what interviewers expect. It demonstrates the ability to recognize patterns in substring counting and convert them into a simple arithmetic formula. Mentioning the brute force idea first shows you understand the problem space, but moving quickly to the O(n) streak-counting method shows strong optimization skills.
This approach involves counting the number of consecutive 1s in segments and using arithmetic calculations to determine the count of all substrings of 1s within those segments. For a segment with k consecutive 1s, the number of substrings is given by k*(k+1)/2. We iterate through the string to find such segments and compute the count accordingly, taking care to apply modulo operation to handle large numbers.
The C solution traverses each character in the string, checking for consecutive '1's. Upon hitting a '0', or at the end of the string, it calculates the number of substrings for the current count of consecutive '1's and resets the counter. The modulo operation ensures that the result stays within the bounds of standard integer representation.
Time Complexity: O(n) as we traverse the string once.
Space Complexity: O(1) as only a fixed number of extra variables are used.
We traverse the string s, using a variable cur to record the current count of consecutive 1s, and a variable ans to record the answer. When we traverse to character s[i], if s[i] = 0, then set cur to 0; otherwise, increment cur by 1, then add cur to ans, and take modulo 10^9 + 7.
After the traversal is complete, return ans.
The time complexity is O(n), where n is the length of the string s. The space complexity is O(1).
Similar problems:
| Approach | Complexity |
|---|---|
| Consecutive Ones Counting and Arithmetic | Time Complexity: O(n) as we traverse the string once. |
| Traversal and Counting | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Substring Expansion | O(n^2) | O(1) | Useful for understanding substring enumeration or when constraints are very small |
| Consecutive Ones Counting + Arithmetic Formula | O(n) | O(1) | Best general solution; single pass counting of runs of ones |
Number of Substrings With Only 1s | 2 Ways | Dry Runs | Leetcode 1513 | codestorywithMIK • codestorywithMIK • 4,183 views views
Watch 9 more video solutions →Practice Number of Substrings With Only 1s with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor