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.
Discussion