[LeetCode] Number of Substrings With Only 1s

1513. Number of Substrings With Only 1s

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.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
int numSub(string s) {
int cnt = 0, res = 0, mod = 1e9 + 7;
for(auto& c : s) {
if(c == '1') cnt++;
else {
res = (res + (cnt + 1) * 1l * cnt / 2 % mod) % mod;
cnt = 0;
}
}
res = (res + (cnt + 1) * 1l * cnt / 2 % mod) % mod;
return res;
}
};
Author: Song Hayoung
Link: https://songhayoung.github.io/2022/01/31/PS/LeetCode/number-of-substrings-with-only-1s/
Copyright Notice: All articles in this blog are licensed under CC BY-NC-SA 4.0 unless stating additionally.