You are given a string s containing “1”s and “0”s. Return the number of substrings that contain only “1”s. Mod the result by 10 ** 9 + 7.
Constraints
0 ≤ n ≤ 100,000 where n is the length of s
Example 1
Input
s = “111001”
Output
7
Explanation
Here are all the substrings containing only “1”s:
“1”
“1”
“1”
`”1″
“11”
“11”
“111”
Split to Ones and Count by Math
If we split the string by ‘0’ and we can get the number of Ones for each group. We know the number of substrings for a size-n ‘1’ string is n(n+1)/2 we then need to sum the numbers of all groups.
1 2 3 4 5 6 | class Solution: def splitAndCount1s(self, s): ans = 0 for i in s.split('0'): ans += len(i) * (len(i) + 1) // 2 return ans |
class Solution:
def splitAndCount1s(self, s):
ans = 0
for i in s.split('0'):
ans += len(i) * (len(i) + 1) // 2
return ans The time complexity is O(N).
–EOF (The Ultimate Computing & Technology Blog) —
GD Star Rating
loading...
204 wordsloading...
Last Post: Teaching Kids Programming - Recursive Algorithm to Determine if a Binary Tree is Symmetric
Next Post: Teaching Kids Programming - Revisit the Symmetric Binary Tree by Using Clone and Invert Algorithm
