Number of Substrings With Only 1s solution and explanation
IBM
Google
9 more videos on this problem
Number of Substrings With Only 1s | 2 Ways | Dry Runs | Leetcode 1513 | codestorywithMIKcodestorywithMIK · 13:49 · 4K views
Number of Substrings With Only 1s - Leetcode 1513 - PythonNeetCodeIO · 7:04 · 4K views
Leetcode 1513 | Number of Substrings with only 1sAbhishek Jaiswal · 7:58 · 371 views
1513. Number of Substrings With Only 1s (Leetcode Medium)Programming Live with Larry · 3:41 · 328 views
Number of Substrings With Only 1s Java Solution | Leetcode 1513Competitive Coding · 4:08 · 310 views
Number of Substrings With Only 1s | LeetCode 1513 | Complete Intutition ExplainedSanyam IIT Guwahati · 9:06 · 274 views
Number of Substrings With Only 1s (Leetcode 1513)Coding Interviews · 22:06 · 251 views
1513. Number of Substrings With Only 1s | Leetcode Daily - PythonLeetcode Daily · 8:12 · 132 views
Number of Substrings With Only 1s | LeetCode 1513 | Java Code | Developer CoderDeveloper Coder · 15:38 · 118 views
Leetcode 1513: Number of Substrings With Only 1s (Python)Raymond Jones · 10:07 · 108 views
The problem
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'.
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.
def numSub(s: str) -> int:
count = 0
result = 0
MOD = 10**9 + 7
for char in s:
if char == '1':
count += 1
else:
result = (result + (count * (count + 1) // 2)) % MOD
count = 0
if count:
result = (result + (count * (count + 1) // 2)) % MOD
return result
s = "0110111"
print(numSub(s)) # Output: 9public class Solution {
public int numSub(String s) {
long count = 0, result = 0;
final int MOD = 1000000007;
for (char c : s.toCharArray()) {
if (c == '1') {
count++;
} else {
result = (result + (count * (count + 1) / 2)) % MOD;
count = 0;
}
}
if (count > 0) {
result = (result + (count * (count + 1) / 2)) % MOD;
}
return (int) result;
}
public static void main(String[] args) {
Solution sol = new Solution();
String s = "0110111";
System.out.println(sol.numSub(s)); // Output: 9
}
}#include <iostream>
#include <string>
using namespace std;
int numSub(string s) {
long count = 0, result = 0;
const int MOD = 1000000007;
for (char c : s) {
if (c == '1') {
count++;
} else {
result = (result + (count * (count + 1) / 2)) % MOD;
count = 0;
}
}
if (count > 0) {
result = (result + (count * (count + 1) / 2)) % MOD;
}
return static_cast<int>(result);
}
int main() {
string s = "0110111";
cout << numSub(s) << endl; // Output: 9
return 0;
}const numSub = function(s) {
let count = 0, result = 0;
const MOD = 1000000007;
for (const char of s) {
if (char === '1') {
count++;
} else {
result = (result + count * (count + 1) / 2) % MOD;
count = 0;
}
}
if (count > 0) {
result = (result + count * (count + 1) / 2) % MOD;
}
return result;
};
console.log(numSub("0110111")); // Output: 9#include <stdio.h>
#define MOD 1000000007
int numSub(char* s) {
long count = 0, result = 0;
for (int i = 0; s[i]; i++) {
if (s[i] == '1') {
count++;
} else {
result = (result + (count * (count + 1) / 2)) % MOD;
count = 0;
}
}
if (count > 0) {
result = (result + (count * (count + 1) / 2)) % MOD;
}
return (int)result;
}
int main() {
char* s = "0110111";
printf("%d\n", numSub(s)); // Output: 9
return 0;
}using System;
public class Solution {
public int NumSub(string s) {
long count = 0, result = 0;
const int MOD = 1000000007;
foreach (char c in s) {
if (c == '1') {
count++;
} else {
result = (result + (count * (count + 1) / 2)) % MOD;
count = 0;
}
}
if (count > 0) {
result = (result + (count * (count + 1) / 2)) % MOD;
}
return (int)result;
}
public static void Main(string[] args) {
Solution sol = new Solution();
Console.WriteLine(sol.NumSub("0110111")); // Output: 9
}
}In the Python implementation, we loop through each character of the string, adding to a count of consecutive '1's, and calculating the number of substrings when a '0' is reached or at the end. This solution leverages Python's flexible integer handling alongside modulo operations to return the correct count.
Time Complexity: O(n) for traversing the input string.
Space Complexity: O(1) since no extra space other than counters is required.
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:
function numSub(s: string): number {
const mod = 1_000_000_007;
let [ans, cur] = [0, 0];
for (const c of s) {
if (c === '0') {
cur = 0;
} else {
cur++;
ans = (ans + cur) % mod;
}
}
return ans;
}func numSub(s string) (ans int) {
const mod int = 1e9 + 7
cur := 0
for _, c := range s {
if c == '0' {
cur = 0
} else {
cur++
ans = (ans + cur) % mod
}
}
return
}impl Solution {
pub fn num_sub(s: String) -> i32 {
const MOD: i32 = 1_000_000_007;
let mut ans: i32 = 0;
let mut cur: i32 = 0;
for c in s.chars() {
if c == '0' {
cur = 0;
} else {
cur += 1;
ans = (ans + cur) % MOD;
}
}
ans
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Consecutive Ones Counting and Arithmetic | Time Complexity: O(n) for traversing the input string. |
| Traversal and Counting | – |
Complexity analysis
| 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 |
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.