Formatted question description: https://leetcode.ca/all/1513.html

# 1513. Number of Substrings With Only 1s (Medium)

Given a binary string s (a string consisting only of '0' and '1's).

Return the number of substrings with all characters 1's.

Since the answer may be too large, return it modulo 10^9 + 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.


Example 4:

Input: s = "000"
Output: 0


Constraints:

• s[i] == '0' or s[i] == '1'
• 1 <= s.length <= 10^5

Related Topics:
Math, String

## Solution 1. Two pointers

Find all the strings formed with all ones. For a substring of length len, there are total = 1 + 2 + ... + len = len * (len + 1) / 2 sub-substrings. The answer is the sum of all the totals mod by 1e9+7.

Since the length of s is at most 1e5, so len * (len + 1) is at most around 1e10 which is greater than what can be hold in a 32bit integer (INT_MAX is 2,147,483,647 ~= 2e9), so we use long long here.

// OJ: https://leetcode.com/problems/number-of-substrings-with-only-1s/

// Time: O(N)
// Space: O(1)
class Solution {
public:
int numSub(string s) {
long long ans = 0, i = 0, N = s.size(), mod = 1e9+7;
while (i < N) {
while (i < N && s[i] == '0') ++i;
long j = i;
while (j < N && s[j] == '1') ++j;
long len = j - i;
ans = (ans + len * (len + 1) / 2 % mod) % mod;
i = j;
}
return ans;
}
};


## Solution 2. Count

// OJ: https://leetcode.com/problems/number-of-substrings-with-only-1s/

// Time: O(N)
// Space: O(1)
class Solution {
public:
int numSub(string s) {
long ans = 0, cnt = 0, mod = 1e9+7;
for (char c : s) {
cnt = c == '1' ? 1 + cnt : 0;
ans = (ans + cnt) % mod;
}
return ans;
}
};


Java

class Solution {
public int numSub(String s) {
final int MODULO = 1000000007;
long total = 0;
int length = s.length();
long consecutive = 0;
for (int i = 0; i < length; i++) {
char c = s.charAt(i);
if (c == '0') {
total += consecutive * (consecutive + 1) / 2;
total %= MODULO;
consecutive = 0;
} else
consecutive++;
}
total += consecutive * (consecutive + 1) / 2;
total %= MODULO;
return (int) total;
}
}