1513.Number of Substrings With Only 1s

Tags: Medium Math String

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

---

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

---

统计全是1的子串（需要连续），首先将字符串切分，提取出全是1的子串，比如第一个测试用例0110111，就切分成11和111两个子串，然后看切分出来的子串能够提取出多少个全是1的子串，假设子串的长是m，那么每个提取出来的子串可以得到m * (m + 1) / 2个全1子串，累加即可。

所以关键在于将字符串切分，pre指向每个全1子串的起始位置，i指向全1子串的末尾，计算出长度m即可完成求解。只需要遍历一遍字符串，时间复杂度$O(n)$。

class Solution {
public:
    int numSub(string s) {
        std::ios_base::sync_with_stdio(false);
        cin.tie(NULL);
        cout.tie(NULL);

        int n = s.size();
        long long res = 0;
        const int MODE = 1e9 + 7;

        int pre = 0;
        for (int i = 0; i < n; ++i) {
            if (s[i] == '1') {
                pre = i;
                while (i < n && s[i] == '1') ++i;
                long long len = i - pre;
                res = (res + (len + 1) * (len) / 2) % MODE;
            }
        }

        return res;
    }
};