Number of Substrings With Only 1s — Problem & Solution
Number of Substrings With Only 1s solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.
Number of Substrings With Only 1s is a medium coding problem on strings and math, asked in Amazon and Google interviews.
- Difficulty: Medium
- Topics: Strings, Math
- Asked at: Amazon, Google
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
Given a binary string s, return the number of its substrings that consist only of 1 characters. Substrings at different positions count separately even when they are equal.
The answer may be large, so return it modulo 10^9 + 7.
Example 1
Input: s = "1101111"
Output: 13
Explanation: The run `11` has 3 such substrings and the run `1111` has 10.
Example 2
Input: s = "000"
Output: 0
Example 3
Input: s = "1111111111"
Output: 55
Constraints
1 <= s.length <= 10^5s[i] is '0' or '1'
Hints for Number of Substrings With Only 1s
Hint 1
Every all-ones substring lies inside one maximal run of ones.
Hint 2
A run of length
LcontainsL·(L+1)/2all-ones substrings.Hint 3
Equivalently, scan once: the number of all-ones substrings ending at position
iis the current run length; add it up modulo 10^9 + 7.
How to solve Number of Substrings With Only 1s
Count the all-ones substrings by their right end: those ending at i number exactly the length of the run of ones ending at i.
Approach
- Keep
run, the number of consecutive1s ending at the current index (reset to 0 on a0). - At each
1, incrementrunand add it to the answer, reducing modulo 10^9 + 7. - Return the answer.
Why it works
An all-ones substring ending at i starts somewhere inside the run that ends at i, and every such start works, so there are run of them; summing over all right ends counts every substring once. Summed over a whole run this is 1 + 2 + … + L = L(L+1)/2. The answer before reduction can reach about 5·10^9, beyond 32 bits, but each step adds at most 10^5 to a value below 10^9 + 7, so reducing as you go keeps every intermediate under 2^31.
Complexity
- Time —
O(n) - Space —
O(1)
Pitfalls
- Computing
L·(L+1)/2in 32-bit arithmetic overflows forLnear 10^5. - Forgetting the modulus: a string of 10^5 ones has 5 000 050 000 such substrings.
- Resetting the run on a
0but forgetting the final run at the end of the string (in the run-length formulation).
Reference solution
Python
def numSub(s: str) -> int:
total = 0
for run in s.split("0"):
n = len(run)
total += n * (n + 1) // 2
return total % 1000000007Java
public static int numSub(String s) {
final int MOD = 1000000007;
int ans = 0, run = 0;
for (int i = 0; i < s.length(); i++) {
if (s.charAt(i) == '1') {
run++;
ans = (ans + run) % MOD;
} else {
run = 0;
}
}
return ans;
}C++
int numSub(string s) {
const int MOD = 1000000007;
int ans = 0, run = 0;
for (char c : s) {
if (c == '1') {
run++;
ans = (ans + run) % MOD;
} else {
run = 0;
}
}
return ans;
}JavaScript
var numSub = function(s) {
var MOD = 1000000007, ans = 0, run = 0;
for (var i = 0; i < s.length; i++) {
if (s.charCodeAt(i) === 49) {
run++;
ans = (ans + run) % MOD;
} else {
run = 0;
}
}
return ans;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 515 strings problems · the whole catalogue
Learn the technique: Strings