Given a binary string s (a string consisting only of '0' and '1's).
Return the number of substrings with all characters 1's.
Since the answer may be too large, return it modulo 10^9 + 7.
 
Example 1:
Input: s = "0110111"
Output: 9
Explanation: There are 9 substring in total with only 1's characters.
"1" -> 5 times.
"11" -> 3 times.
"111" -> 1 time.
Example 2:
Input: s = "101"
Output: 2
Explanation: Substring "1" is shown 2 times in s.

Example 3:
Input: s = "111111"
Output: 21
Explanation: Each substring contains only 1's characters.

Example 4:
Input: s = "000"
Output: 0

 
Constraints:

s[i] == '0' or s[i] == '1'
1 <= s.length <= 10^5

Source: leetcode | Difficulty: MEDIUM_HARD
Tags: String algorithms

Mathematics

Starter code: class Solution:
    def numSub(self, s: str) -> int:
        

Solutions:
class Solution:

	def numSub(self, s: str) -> int:
		dic = collections.defaultdict(int)
		n = len(s)
		(left, right) = (0, 0)
		while left < n:
			if s[left] == '1':
				right = left
				while right < n and s[right] == '1':
					right += 1
				dic[right - left] += 1
				left = right
			else:
				left += 1
		total = 0
		for ones in dic:
			total = (total + ones * (ones + 1) // 2 * dic[ones]) % (10 ** 9 + 7)
		return total


class Solution:

	def calc_num_variations(self, num_ones, memo):
		if num_ones in memo:
			return memo[num_ones]
		curr_sum = 0
		for x in range(num_ones + 1):
			curr_sum += x
			if not x in memo:
				memo[x] = curr_sum
		memo[num_ones] = curr_sum
		return curr_sum

	def numSub(self, s: str) -> int:
		memo = {}
		num_ones = 0
		num_variations = 0
		for one in s:
			if one == '1':
				num_ones += 1
			else:
				num_variations += self.calc_num_variations(num_ones, memo)
				num_ones = 0
		if num_ones > 0:
			num_variations += self.calc_num_variations(num_ones, memo)
		return num_variations % (10 ** 9 + 7)


class Solution:

	def numSub(self, s: str) -> int:
		res = 0
		i = 0
		mod = int(1000000000.0 + 7)
		while i < len(s):
			if s[i] != '1':
				i += 1
				continue
			start = i
			while i < len(s) and s[i] == '1':
				i += 1
			count = i - start
			res += count * (count + 1) / 2
			res %= mod
		return int(res)


class Solution:

	def numSub(self, s: str) -> int:
		res = 0
		mod = pow(10, 9) + 7
		i = 0
		while i < len(s):
			cnt = 0
			while i < len(s) and s[i] == '1':
				cnt += 1
				i += 1
			i += 1
			res += cnt * (cnt + 1) // 2 % mod
		return res


class Solution:

	def numSub(self, s: str) -> int:
		n = len(s)
		start = 0
		while start < n and s[start] != '1':
			start += 1
		if start == n:
			return 0
		i = start
		count = 0
		while i < n and start < n:
			if s[i] == '1':
				count += i - start + 1
				count = count % (10 ** 9 + 7)
				i += 1
				continue
			start = i
			while start < n and s[start] != '1':
				start += 1
			i = start
		return count


class Solution:

	def numSub(self, s: str) -> int:
		(result, stop_idx) = (0, -1)
		for (idx, char) in enumerate(s):
			if char != '1' or idx <= stop_idx:
				continue
			freq = 1
			next_idx = idx + 1
			while next_idx < len(s) and s[next_idx] == '1':
				freq += 1
				stop_idx = next_idx
				next_idx += 1
			result += (freq + 1) * freq / 2
		return int(result % (1000000000.0 + 7))


class Solution:

	def numSub(self, s: str) -> int:
		cont_one_count = 0
		one_sub = 0
		for char in s:
			if char == '1':
				cont_one_count += 1
			if char == '0':
				one_sub += cont_one_count * (cont_one_count + 1) / 2
				cont_one_count = 0
		one_sub += cont_one_count * (cont_one_count + 1) / 2
		return int(one_sub) % (10 ** 9 + 7)


class Solution:

	def numSub(self, s: str) -> int:
		self.s = s
		modulo = 1000000007

		def numSub(s):
			sOne = ''
			sSub = []
			for i in range(len(s)):
				if s[i] == '1':
					sOne += '1'
					if i != len(s) - 1:
						if s[i + 1] == '1':
							continue
						else:
							sSub.append(sOne)
							sOne = ''
					else:
						sSub.append(sOne)
			return sSub
		sSub = numSub(s)
		num_sOne = 0
		for sOne in sSub:
			len_sOne = len(sOne)
			num_sOne += len_sOne * (len_sOne + 1) // 2 % modulo
		num_sOne %= modulo
		return int(num_sOne)


class Solution:

	def numSub(self, s: str) -> int:
		num_lst = []
		ans = 0
		temp = 0
		for n in s:
			if n == '1':
				temp += 1
			if n == '0' and temp != 0:
				num_lst.append(temp)
				temp = 0
		if temp != 0:
			num_lst.append(temp)
		if len(num_lst) == 0:
			return 0
		for num in num_lst:
			while num != 0:
				ans += num
				num -= 1
		return ans % (10 ** 9 + 7)


class Solution:

	def numSub(self, s: str) -> int:
		n = len(s)
		i = 0
		count = 0
		while i < n:
			if s[i] == '1':
				seq = 0
				while i < n and s[i] == '1':
					seq += 1
					i += 1
				count += seq * (seq + 1) // 2
			else:
				i += 1
		print(count % (10 ** 9 + 7))
		return count % (10 ** 9 + 7)


class Solution:

	def numSub(self, s: str) -> int:
		sum = cnt = 0
		for c in s:
			if c == '1':
				cnt += 1
				sum = (sum + cnt) % (10 ** 9 + 7)
			else:
				cnt = 0
		return sum