Given a binary string S consists only of 0s and 1s. The task is to calculate the number of substrings that have more 1s than 0s.
Example 1:
Input:
S = "011"
Output: 4
Explanation: There are 4 substring which 
has more 1s than 0s. i.e "011","1","11" and "1"
Example 2:
Input:
S = "0000"
Output: 0
Explanation: There is no substring
which has more 1s than 0s
Your Task:  
You dont need to read input or print anything. Complete the function countSubstring() which takes the string S as input parameter and returns the number of substring which has more 1s than 0s.
Expected Time Complexity: O(|S|)
Expected Auxiliary Space: O(|S|)
Constraints:
1 < |S| < 10^{5}
|S| denotes the length of the string S

Difficulty: MEDIUM_HARD
Tags: String algorithms

Dynamic programming

Data structures
Skill types: Dynamic programming

Data structures
Expected Time Complexity: O(|S|)
Expected Auxiliary Space: O(|S|)

Starter code:
#User function Template for python3





class Solution():

    def countSubstring(self, S):

        #your code here

Solutions:
class Solution:

	def countSubstring(self, S):
		n = len(S)
		dp = [0] * (2 * n + 1)
		(minius, count) = (0, n)
		for i in range(n):
			if S[i] == '0':
				count -= 1
			else:
				count += 1
			if count <= n:
				minius += 1
			dp[count] += 1
		ans = 0
		ind = n
		for i in range(n):
			ans += n - i - minius
			if S[i] == '1':
				ind += 1
				dp[ind] -= 1
				minius += dp[ind]
			else:
				minius -= 1
				minius -= dp[ind]
				ind -= 1
				dp[ind] -= 1
		return ans


from collections import defaultdict

class Solution:

	def countSubstring(self, S):
		x1 = defaultdict(int)
		x2 = defaultdict(int)
		count = 0
		x1[0] = 1
		x2[1] = 1
		ans = 0
		for i in S:
			if i == '1':
				ones = 1
			else:
				ones = -1
			count = count + ones
			x1[count] += 1 + x2[count]
			x2[count + 1] += 1 + x2[count]
			x2[count] = 0
			ans = ans + x1[count - 1]
		return ans


class Solution:

	def countSubstring(self, S):
		n = len(S)
		ans = 0
		zero = n
		minus = 0
		mp = [0] * (2 * n + 5)
		cur = zero
		for i in S:
			if i == '0':
				cur -= 1
			else:
				cur += 1
			if cur <= zero:
				minus += 1
			mp[cur] += 1
		for i in range(n):
			ans += n - i - minus
			if S[i] == '1':
				mp[zero + 1] -= 1
				zero += 1
				minus += mp[zero]
			else:
				mp[zero - 1] -= 1
				zero -= 1
				minus -= 1
				minus -= mp[zero + 1]
		return ans


from collections import Counter

class Solution:

	def countSubstring(self, S):
		ans = 0
		temp = Counter()
		summ = 0
		var = 0
		for s in S:
			i = 1 if s == '1' else -1
			summ += i
			temp[summ] += 1
			if summ > 0:
				var += 1
		ans += var
		summ = 0
		for s in S:
			i = 1 if s == '1' else -1
			summ += i
			if i == 1:
				var -= temp[summ]
			if i == -1:
				var += temp[summ + 1]
			temp[summ] -= 1
			ans += var
		return ans


import sys
sys.setrecursionlimit = 100000
from collections import deque

class Solution:

	def countSubstring(self, S):
		n = len(s)
		dp = [0] * (2 * n + 1)
		(minius, count) = (0, n)
		for i in range(n):
			if s[i] == '0':
				count -= 1
			else:
				count += 1
			if count <= n:
				minius += 1
			dp[count] += 1
		ans = 0
		ind = n
		for i in range(n):
			ans += n - i - minius
			if s[i] == '1':
				ind += 1
				dp[ind] -= 1
				minius += dp[ind]
			else:
				minius -= 1
				minius -= dp[ind]
				ind -= 1
				dp[ind] -= 1
		return ans


from collections import defaultdict

class Solution:

	def countSubstring(self, S):
		(acc, le, carry) = (0, defaultdict(lambda : 0), defaultdict(lambda : 0))
		le[0] = 1
		carry[1] = 1
		ans = 0
		for c in S:
			v = 1 if c == '1' else -1
			acc += v
			le[acc] += 1 + carry[acc]
			carry[acc + 1] += 1 + carry[acc]
			carry[acc] = 0
			ans += le[acc - 1]
		return ans


class Solution:

	def countSubstring(self, S):
		new = []
		count = 0
		cur_sum = 0
		for i in S:
			if i == '1':
				cur_sum += 1
			else:
				cur_sum -= 1
			new.append(cur_sum)
			if cur_sum > 0:
				count += 1

		def mergesort(S):
			if len(S) == 1:
				return (S, 0)
			mid = len(S) // 2
			(left, left_count) = mergesort(S[:mid])
			(right, right_count) = mergesort(S[mid:])
			(final, final_count) = merge(left, right)
			return (final, left_count + final_count + right_count)

		def merge(l1, l2):
			ct = 0
			new = []
			(n1, n2) = (0, 0)
			(m1, m2) = (len(l1), len(l2))
			while n1 < m1 and n2 < m2:
				if l1[n1] < l2[n2]:
					ct += m2 - n2
					new.append(l1[n1])
					n1 += 1
				else:
					new.append(l2[n2])
					n2 += 1
			new = new + l1[n1:] + l2[n2:]
			return (new, ct)
		(st, ans) = mergesort(new)
		return ans + count


class Solution:

	def countSubstring(self, a):
		mid_pointer = len(a)
		dp = [0] * (2 * len(a) + 1)
		cnt = mid_pointer
		minus = 0
		for i in range(len(a)):
			if a[i] == '1':
				cnt += 1
			else:
				cnt -= 1
			if cnt <= mid_pointer:
				minus += 1
			dp[cnt] += 1
		idx = mid_pointer
		ans = 0
		for i in range(len(a)):
			ans += len(a) - i - minus
			if a[i] == '1':
				idx += 1
				dp[idx] -= 1
				minus += dp[idx]
				pass
			else:
				minus -= 1
				minus -= dp[idx]
				idx -= 1
				dp[idx] -= 1
		return ans


class Solution:

	def __init__(self):
		self.invCnt = 0

	def merge(self, arr, s, e, mid):
		arr1 = arr[s:mid + 1]
		arr2 = arr[mid + 1:e + 1]
		imax = mid - s + 1
		jmax = e - mid
		i = 0
		j = 0
		k = s
		while i < imax and j < jmax:
			if arr1[i] >= arr2[j]:
				arr[k] = arr1[i]
				i += 1
			else:
				self.invCnt += imax - i
				arr[k] = arr2[j]
				j += 1
			k += 1
		while i < imax:
			arr[k] = arr1[i]
			i += 1
			k += 1
		while j < jmax:
			arr[k] = arr2[j]
			j += 1
			k += 1

	def mergeSort(self, arr, s, e):
		if s < e:
			mid = (s + e) // 2
			self.mergeSort(arr, s, mid)
			self.mergeSort(arr, mid + 1, e)
			self.merge(arr, s, e, mid)

	def inversionCount(self, arr, n):
		self.mergeSort(arr, 0, n - 1)
		return self.invCnt

	def countSubstring(self, S):
		N = len(S)
		dp = [0] * N
		cnt = 0
		i = 0
		for v in S:
			if v == '0':
				if i == 0:
					dp[i] = -1
				else:
					dp[i] = dp[i - 1] - 1
			elif i == 0:
				dp[i] = 1
			else:
				dp[i] = dp[i - 1] + 1
			if dp[i] > 0:
				cnt += 1
			i += 1
		self.inversionCount(dp, i)
		return self.invCnt + cnt


import math
from collections import defaultdict

class Solution:

	def countSubstring(self, S):
		n = len(S)
		ones = int(S[0] == '1')
		zeros = int(S[0] == '0')
		ans = [0 for i in range(n)]
		ans[0] = ones
		one_zero_map = defaultdict(int)
		one_zero_map[ones - zeros] += 1
		one_zero_map[0] += 1
		for i in range(1, n):
			if S[i] == '1':
				ans[i] = ans[i - 1] + 1
				ans[i] += one_zero_map[ones - zeros] - 1
				ones += 1
			else:
				ans[i] = ans[i - 1]
				ans[i] -= one_zero_map[ones - zeros - 1]
				zeros += 1
			one_zero_map[ones - zeros] += 1
		return sum(ans)


class Solution:

	def countSubstring(self, S):
		res = 0
		levels = {0: [1, 0]}
		level = 0
		for s in S:
			x = 1 if s == '1' else -1
			newLevel = level - x
			if newLevel not in levels.keys():
				if x == -1:
					levels[newLevel] = [1, 0]
				else:
					levels[newLevel] = [1, sum(levels[level])]
			elif x == -1:
				levels[newLevel][0] += 1
			else:
				levels[newLevel] = [levels[newLevel][0] + 1, sum(levels[level])]
			res += levels[newLevel][1]
			level = newLevel
		return res


class Solution:

	def countSubstring(self, S):
		n = len(S)
		if '1' not in S:
			return 0
		elif '0' not in S:
			return int(n * (n + 1) / 2)

		def merge(arr, temp_arr, left, mid, right):
			i = left
			j = mid + 1
			k = left
			inv_count = 0
			while i <= mid and j <= right:
				if arr[i] <= arr[j]:
					temp_arr[k] = arr[i]
					k += 1
					i += 1
				else:
					temp_arr[k] = arr[j]
					inv_count += mid - i + 1
					k += 1
					j += 1
			while i <= mid:
				temp_arr[k] = arr[i]
				k += 1
				i += 1
			while j <= right:
				temp_arr[k] = arr[j]
				k += 1
				j += 1
			for loop_var in range(left, right + 1):
				arr[loop_var] = temp_arr[loop_var]
			return inv_count

		def _mergeSort(arr, temp_arr, left, right):
			inv_count = 0
			if left < right:
				mid = (left + right) // 2
				inv_count += _mergeSort(arr, temp_arr, left, mid)
				inv_count += _mergeSort(arr, temp_arr, mid + 1, right)
				inv_count += merge(arr, temp_arr, left, mid, right)
			return inv_count

		def mergeSort(arr, n):
			temp_arr = [0] * n
			return _mergeSort(arr, temp_arr, 0, n - 1)
		pref = [0 for i in range(n)]
		for i in range(n):
			if S[i] == '0':
				pref[i] = -1
			else:
				pref[i] = 1
		for i in range(1, n):
			pref[i] += pref[i - 1]
		count = 0
		for i in range(n):
			if pref[i] > 0:
				count += 1
		j = n - 1
		i = 0
		while i < j:
			(pref[i], pref[j]) = (pref[j], pref[i])
			i += 1
			j -= 1
		return count + mergeSort(pref, n)


class Solution:

	def countSubstring(self, S):
		ans = 0
		total = 0
		below = 0
		d = {0: 1}
		for ch in S:
			if ch == '1':
				total += 1
				below += d.get(total - 1, 0)
			else:
				total -= 1
				below -= d.get(total, 0)
			ans += below
			d[total] = d.get(total, 0) + 1
		return ans


from collections import Counter

class Solution:

	def countSubstring(self, S):
		ans = 0
		dp = Counter()
		ssum = 0
		num_pos = 0
		for s in S:
			i = 1 if s == '1' else -1
			ssum += i
			dp[ssum] += 1
			if ssum > 0:
				num_pos += 1
		ans += num_pos
		ssum = 0
		for s in S:
			i = 1 if s == '1' else -1
			ssum += i
			if i == 1:
				num_pos -= dp[ssum]
			if i == -1:
				num_pos += dp[ssum + 1]
			dp[ssum] -= 1
			ans += num_pos
		return ans


class Solution:

	def countSubstring(self, S):
		nums = [1 if ch == '1' else -1 for ch in S]
		pref_sum = [0] * len(nums)
		pref_sum[0] = nums[0]
		for i in range(1, len(nums)):
			pref_sum[i] = pref_sum[i - 1] + nums[i]
		pref_sum.insert(0, 0)
		count = countSums(pref_sum)
		return count

def countSums(pref_sum):
	return countHelper(pref_sum, 0, len(pref_sum) - 1)

def countHelper(arr, left, right):
	if left == right:
		return 0
	mid = (left + right) // 2
	count1 = countHelper(arr, left, mid)
	count2 = countHelper(arr, mid + 1, right)
	count = count1 + count2
	l_arr = arr[left:mid + 1]
	r_arr = arr[mid + 1:right + 1]
	l_arr.sort()
	r_arr.sort()
	i = len(l_arr) - 1
	j = len(r_arr) - 1
	while i >= 0 and j >= 0:
		if l_arr[i] < r_arr[j]:
			count += i + 1
			j -= 1
		else:
			i -= 1
	return count


from collections import defaultdict

class Solution:

	def countSubstring(self, S):
		ans = 0
		s = 0
		belowSum = 0
		d = defaultdict(int)
		d[0] += 1
		for i in S:
			s = s + 1 if i == '1' else s - 1
			belowSum = belowSum - d[s] if i == '0' else belowSum + d[s - 1]
			ans += belowSum
			d[s] += 1
		return ans


class Solution:

	def countSubstring(self, S):
		c = 0
		ans = 0
		n = len(S)
		freq = []
		dp = []
		for i in range(2 * n + 2):
			freq.append(0)
			dp.append(0)
		freq[n] += 1
		for i in S:
			if i == '0':
				c -= 1
			else:
				c += 1
			if c - 1 + n >= 0:
				dp[c + n] = dp[c - 1 + n] + freq[c - 1 + n]
				ans += dp[c + n]
				freq[c + n] += 1
		return ans


class Solution:

	def countSubstring(self, S):
		n = len(s)
		dibba = [0] * (2 * n + 1)
		(Mini, c) = (0, n)
		for i in range(n):
			if s[i] == '0':
				c -= 1
			else:
				c += 1
			if c <= n:
				Mini += 1
			dibba[c] += 1
		result = 0
		tea = n
		for i in range(n):
			result += n - i - Mini
			if s[i] == '1':
				tea += 1
				dibba[tea] -= 1
				Mini += dibba[tea]
			else:
				Mini -= 1
				Mini -= dibba[tea]
				tea -= 1
				dibba[tea] -= 1
		return result


class Solution:

	def countSubstring(self, S):
		n = len(s)
		dp = [0] * (2 * n + 1)
		(minius, count) = (0, n)
		for i in range(n):
			if s[i] == '0':
				count -= 1
			else:
				count += 1
			if count <= n:
				minius += 1
			dp[count] += 1
		ans = 0
		ind = n
		for i in range(n):
			ans += n - i - minius
			if s[i] == '1':
				ind += 1
				dp[ind] -= 1
				minius += dp[ind]
			else:
				minius -= 1
				minius -= dp[ind]
				ind -= 1
				dp[ind] -= 1
		return ans
if __name__ == '__main__':
	for _ in range(int(input())):
		s = input()
		print(Solution().countSubstring(s))


class Solution:

	def countSubstring(self, S):
		ans = 0
		cnt = 0
		si = len(S)
		dp = [0] * (2 * si + 2)
		freq = [0] * (2 * si + 2)
		freq[si] += 1
		for i in S:
			if i == '0':
				cnt -= 1
			else:
				cnt += 1
			if cnt - 1 + si >= 0:
				dp[cnt + si] = dp[cnt - 1 + si] + freq[cnt - 1 + si]
				ans += dp[cnt + si]
				freq[cnt + si] += 1
		return ans


from collections import defaultdict

class Solution:

	def countSubstring(self, S):
		if S.count('1') == 1:
			return 1
		if '1' not in S:
			return 0
		if '0' not in S:
			return len(S) * (len(S) + 1) // 2
		dic = defaultdict(int)
		(sm, neg_count) = (0, 0)
		for ele in S:
			if ele == '1':
				sm += 1
			else:
				sm -= 1
			dic[sm] += 1
			if sm <= 0:
				neg_count += 1
		(sm, ans) = (0, 0)
		for i in range(len(S)):
			ans += len(S) - i - neg_count
			if S[i] == '1':
				sm += 1
				dic[sm] -= 1
				neg_count += dic[sm]
			else:
				sm -= 1
				dic[sm] -= 1
				neg_count -= 1
				neg_count -= dic[sm + 1]
		return ans