1513. Number of Substrings With Only 1s

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/
// Author: github.com/lzl124631x
// 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/
// Author: github.com/lzl124631x
// 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;
    }
};