Today I have done leetcode's November LeetCoding Challenge with cpp.

November LeetCoding Challenge 16

Description

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.

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.

Constraints:

• 1 <= s.length <= 105
• s[i] is either '0' or '1'.

Solution

class Solution {
  const int MOD = 1e9 + 7;
public:
  int numSub(string s) {
    int ones = 0;
    int answer = 0;
    for(auto c : s) {
      if(c == '1') {
        ones += 1;
        continue;
      }
      answer += 1LL * ones * (ones + 1) / 2 % MOD;
      answer %= MOD;
      ones = 0;
    }
    answer += 1LL * ones * (ones + 1) / 2 % MOD;
    answer %= MOD;
    return answer;
  }
};

// Accepted
// 56/56 cases passed (0 ms)
// Your runtime beats 100 % of cpp submissions
// Your memory usage beats 72.24 % of cpp submissions (11.6 MB)