Count Number of Substrings with Only 1s

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.