Number of Substrings With Only 1s

medium string math counting

Problem

Given a binary string s, return the number of substrings whose characters are all 1. The answer may be large, so return it modulo 10⁹ + 7.

Inputs = "0110111"

Output9

"1" appears 5 times, "11" 3 times, "111" once: 5 + 3 + 1 = 9.

Inputs = "111111"

Output21

A single run of length 6 gives 6·7/2 = 21 all-ones substrings.

s (binary string)

def num_sub(s):
    MOD = 10**9 + 7
    ans = 0
    count = 0
    for ch in s:
        if ch == '1':
            count += 1
            ans = (ans + count) % MOD
        else:
            count = 0
    return ans

function numSub(s) {
  const MOD = 1000000007n;
  let ans = 0n, count = 0n;
  for (const ch of s) {
    if (ch === '1') {
      count += 1n;
      ans = (ans + count) % MOD;
    } else {
      count = 0n;
    }
  }
  return Number(ans);
}

int numSub(String s) {
    final int MOD = 1_000_000_007;
    long ans = 0, count = 0;
    for (int i = 0; i < s.length(); i++) {
        if (s.charAt(i) == '1') {
            count++;
            ans = (ans + count) % MOD;
        } else {
            count = 0;
        }
    }
    return (int) ans;
}

int numSub(string s) {
    const long long MOD = 1000000007;
    long long ans = 0, count = 0;
    for (char ch : s) {
        if (ch == '1') {
            count++;
            ans = (ans + count) % MOD;
        } else {
            count = 0;
        }
    }
    return (int) ans;
}

Explanation

Every all-ones substring lives entirely inside one maximal run of consecutive 1s. A run of length k contains exactly 1 + 2 + … + k = k(k+1)/2 such substrings, so the total answer is the sum of k(k+1)/2 over all runs.

Instead of finding runs first, we fold that sum into a single left-to-right pass. We keep count = the length of the current run of 1s ending at the character we just read.

When the current character is 1, the run grows by one, so count increases by 1. The new character ends exactly count new all-ones substrings (one for each start position inside the current run), so we add count to ans.

When the character is 0, the run is broken, so we reset count to 0. Because ans += count with count running 1, 2, …, k across a run automatically yields 1 + 2 + … + k = k(k+1)/2, this matches the closed form.

We take the result modulo 10⁹ + 7 after each addition to keep it within range. The whole algorithm is a single linear scan with constant extra memory.

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