Given a binary string, count no of substrings with only 1’s. Since the resulting count can be huge, return it modulo .
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 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: where is the length of string.
- Space Complexity: as we are not using any extra space.