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.

Description Hints 1 Solution Video 13:49

1513. Number of Substrings With Only 1s

Medium57.4% acceptance3 companies

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 10⁹ + 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 <= 10⁵
s[i] is either '0' or '1'.

Asked at 3 companies

IBM

Google Amazon

Topics

Math String

Hints open one at a time

Hint 1

Count number of 1s in each consecutive-1 group. For a group with n consecutive 1s, the total contribution of it to the final answer is (n + 1) * n // 2.

13:49

Still stuck?Read 2 approaches, or watch a walkthrough.

Open solution