Problem

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 10^9 + 7.

Examples

Example 1

1
2
3
4
5
6

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

1
2
3

Input: s = "101"
Output: 2
Explanation: Substring "1" is shown 2 times in s.

Example 3

1
2
3

Input: s = "111111"
Output: 21
Explanation: Each substring contains only 1's characters.

Constraints

  • 1 <= s.length <= 10^5
  • s[i] is either '0' or '1'.

Solution

Method 1 – Count Consecutive 1’s

Intuition

For each run of consecutive 1’s of length k, the number of substrings with only 1’s is k*(k+1)/2. We can scan the string and sum this for each run.

Approach

  1. Initialize count = 0, ans = 0.
  2. For each character in s:
    • If ‘1’, increment count.
    • If ‘0’, add count*(count+1)//2 to ans, reset count to 0.
  3. After the loop, add the last run if needed.
  4. Return ans modulo 1e9+7.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

class Solution {
public:
    int numSub(string s) {
        const int MOD = 1e9+7;
        long ans = 0, cnt = 0;
        for (char c : s) {
            if (c == '1') cnt++;
            else { ans += cnt * (cnt + 1) / 2; cnt = 0; }
        }
        ans += cnt * (cnt + 1) / 2;
        return ans % MOD;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

func numSub(s string) int {
    mod := int(1e9+7)
    ans, cnt := 0, 0
    for _, c := range s {
        if c == '1' {
            cnt++
        } else {
            ans = (ans + cnt*(cnt+1)/2) % mod
            cnt = 0
        }
    }
    ans = (ans + cnt*(cnt+1)/2) % mod
    return ans
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

class Solution {
    public int numSub(String s) {
        int MOD = 1_000_000_007;
        long ans = 0, cnt = 0;
        for (char c : s.toCharArray()) {
            if (c == '1') cnt++;
            else { ans += cnt * (cnt + 1) / 2; cnt = 0; }
        }
        ans += cnt * (cnt + 1) / 2;
        return (int)(ans % MOD);
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

class Solution {
    fun numSub(s: String): Int {
        val MOD = 1_000_000_007
        var ans = 0L
        var cnt = 0L
        for (c in s) {
            if (c == '1') cnt++
            else { ans = (ans + cnt * (cnt + 1) / 2) % MOD; cnt = 0 }
        }
        ans = (ans + cnt * (cnt + 1) / 2) % MOD
        return ans.toInt()
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

class Solution:
    def numSub(self, s: str) -> int:
        MOD = 10**9 + 7
        ans = cnt = 0
        for c in s:
            if c == '1':
                cnt += 1
            else:
                ans += cnt * (cnt + 1) // 2
                cnt = 0
        ans += cnt * (cnt + 1) // 2
        return ans % MOD
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

impl Solution {
    pub fn num_sub(s: String) -> i32 {
        let m = 1_000_000_007;
        let mut ans = 0i64;
        let mut cnt = 0i64;
        for c in s.chars() {
            if c == '1' {
                cnt += 1;
            } else {
                ans = (ans + cnt * (cnt + 1) / 2) % m;
                cnt = 0;
            }
        }
        ans = (ans + cnt * (cnt + 1) / 2) % m;
        ans as i32
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

class Solution {
    numSub(s: string): number {
        const MOD = 1e9+7
        let ans = 0, cnt = 0
        for (const c of s) {
            if (c === '1') cnt++
            else { ans = (ans + cnt*(cnt+1)/2) % MOD; cnt = 0 }
        }
        ans = (ans + cnt*(cnt+1)/2) % MOD
        return ans
    }
}

Complexity

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