Skip to main content
Talentd

Number of Substrings With Only 1s - Solution & Explanation

MediumMathString13 min readAsked at: Amazon, IBM, Google
Practice this problem

Problem Statement

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 <= 105
  • s[i] is either '0' or '1'.

Approach Overview

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.

Approach 1: Consecutive Ones Counting and Arithmetic

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.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n) as we traverse the string once.
Space Complexity: O(1) as only a fixed number of extra variables are used.

Try this approach in the editor →

Approach 2: Traversal and Counting

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:

Code

PythonJavaC++GoTypeScriptRust

Python

Java

C++

Go

TypeScript

Rust

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Consecutive Ones Counting and Arithmetic

Time Complexity: O(n) as we traverse the string once.
Space Complexity: O(1) as only a fixed number of extra variables are used.

Traversal and Counting—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force Substring ExpansionO(n^2)O(1)Useful for understanding substring enumeration or when constraints are very small
Consecutive Ones Counting + Arithmetic FormulaO(n)O(1)Best general solution; single pass counting of runs of ones

Video Solution

Number of Substrings With Only 1s | 2 Ways | Dry Runs | Leetcode 1513 | codestorywithMIK • codestorywithMIK • 4,440 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Number of Substrings With Only 1s easy or hard?
The problem is rated Medium because the brute force idea is simple but recognizing the arithmetic pattern in consecutive runs of ones requires insight. Once you see that a run of length k contributes k*(k+1)/2 substrings, the implementation becomes straightforward and linear.
Number of Substrings With Only 1s Python/Java solution
The implementation is identical across languages: iterate through the string, maintain a counter for consecutive '1's, add the counter to the result at each step, and reset when a '0' appears. The final result is returned modulo 1e9+7. This pattern works cleanly in Python, Java, C++, JavaScript, and C#.
How to solve Number of Substrings With Only 1s in O(n)?
Traverse the string once and track the current count of consecutive '1's. When you encounter '1', increment the streak and add it to the result because it forms new substrings ending at that index. When a '0' appears, reset the streak to zero. Apply modulo 1e9+7 to keep the result within bounds.
What is the best approach for Number of Substrings With Only 1s?
The optimal approach counts consecutive runs of '1's while scanning the string once. If the current streak length is k, add k to the total because each new '1' forms k substrings ending at that position. This produces the same result as the formula k*(k+1)/2 for each block of ones but computed incrementally in O(n) time and O(1) space.
Is Number of Substrings With Only 1s asked at Google/Amazon/Meta?
Substring counting and pattern recognition problems frequently appear in interviews at companies like Amazon, Google, and Meta. Variants that involve counting valid substrings, runs of characters, or combinatorial counting within strings are common in coding rounds.
What data structure is used in Number of Substrings With Only 1s?
No complex data structure is required. The solution processes the string sequentially and uses simple integer counters to track the length of the current run of ones and the accumulated result.
What is the time complexity of Number of Substrings With Only 1s?
The optimal solution runs in O(n) time because it performs a single pass through the string while maintaining the length of the current consecutive ones streak. Space complexity is O(1) since only a few integer counters are stored regardless of input size.

Ready to solve this problem?

Practice Number of Substrings With Only 1s with our built-in code editor and test cases.

Practice on FleetCode
Previous

Count Number of Homogenous Substrings

Next

Count Vowel Substrings of a String