Algorithm to Count the Number of Substrings With Only 1s

Given a binary string s (a string consisting only of ‘0’ and ‘1’s). Return the number of substrings with all characters 1’s. Since the answer may be too large, return it modulo 10^9 + 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.

Example 4:
Input: s = “000”
Output: 0

Constraints:
s[i] == ‘0’ or s[i] == ‘1’
1 <= s.length <= 10^5

Hints:
Count number of 1s in each consecutive-1 group. For a group with n consecutive 1s, the total contribution of it to the final answer is (n + 1) * n // 2.

Count the Number of Substrings With Only 1s

Given a string that is size of n and contains only consecutive-ones, the total contribution to the final answer is (n+1)*n//2. Thus, we can split the origin string by ‘0’, then sum up the each individuals.

1
2
3
4
5
6
7

class Solution:
    def numSub(self, s: str) -> int:
        arr = s.split('0')
        res = 0
        for i in arr:
            res += (len(i) + 1) * len(i) // 2
        return int(res % (1e9 + 7))

class Solution:
    def numSub(self, s: str) -> int:
        arr = s.split('0')
        res = 0
        for i in arr:
            res += (len(i) + 1) * len(i) // 2
        return int(res % (1e9 + 7))

This (Math Solution) is far superior than the bruteforce algorithm where you enumerate all pairs in O(N^2) quadric time of substrings and check if each substring contains only 1’s (which will take O(N^3) all together).

The above solution runs at O(N) time and O(N) space – i.e. space required for spliting a string.

–EOF (The Ultimate Computing & Technology Blog) —