1513. Number of Substrings With Only 1s

Description

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'.

 

Solutions

Solution: Math

• Time complexity: O(n)
• Space complexity: O(1)

 

JavaScript

/**
 * @param {string} s
 * @return {number}
 */
const numSub = function (s) {
  const MODULO = 10 ** 9 + 7;
  let result = (current = subCount = 0);

  for (let index = 0; index <= s.length; index++) {
    const char = s[index];

    if (char === '1') {
      subCount += 1;
      current += subCount;
      continue;
    }
    result = (result + current) % MODULO;
    current = subCount = 0;
  }
  return result;
};