# Count Number of Substrings with Only 1s

Ayan Banerjee Originally published at notescs.gitlab.io on ・2 min read

Given a binary string, count no of substrings with only 1’s. Since the resulting count could be huge, print it modulo $10^9 + 7$ .

Example :

Input: “11101101”

Output: 10

Explanation: “1” occurs 6 times, “11” occurs 3 times and “111” occurs 1 time. Thus number of substrings with only 1’s = 6 + 3 + 1 = 10.

## Approach: Sliding Window

### Intuition

We can see that a ‘0’ divides two blocks of ‘1’s. For a block of ‘1’ with length l has $1 + 2 + 3 + ... + l = l * (l + 1) / 2$ substrings. Thus, we only need to count the length of each block of 1’s and use the above formula.

For example, the string “11101101” can be divided into blocks of 1’s having 3 characters, 2 characters and 1 character which will give 3 * (3 + 1) / 2 = 6, 2 * (2 + 1) / 2 = 3 and 1 * (1 + 1) / 2 = 1 substring respectively.

### Implementation

C++ code:

#include <iostream>
#include <string>
using namespace std;

int subCount(string s) {
const int MOD = 1e9 + 7;
int i = 0, l = s.length();
int ans = 0;
while (i < l) {
int count = 0; // count gives length of block of 1's
if (s[i] == '1') {
while(i < l and s[i] == '1') {
++count;
++i;
}
long substringCount = 1L * count * (count + 1) / 2 % MOD;
ans = (ans + substringCount) % MOD;
} else {
++i;
}
}
return ans;
}

int main() {
cout << "Number of substring with only 1's for 11101101 is " << subCount("11101101") << endl;
return 0;
}


Python code:

def sub_count(s):
MOD = 10**9 + 7
i = 0
l = len(s)
ans = 0
while i < l:
if s[i] == '1':
count = 0 # count gives length of block of 1's
while i < l and s[i] == '1':
count += 1
i += 1
substring_count = count * (count + 1) // 2 % MOD
ans = (ans + substring_count) % MOD
else:
i += 1
return ans

if __name__ == ' __main__':
print("Number of substring with only 1's for 11101101 is", sub_count('11101101'))


### Complexity Analysis

• Time Complexity: $O(n)$ where n is the length of string.
• Space Complexity: $O(1)$ as we are not using any extra space.

Posted on by: