Given a string str of length N which consists of only 0, 1 or 2s, count the number of substring which have equal number of 0s, 1s and 2s.
 
Example 1:
Input: str = “0102010”
Output: 2
Explanation: Substring str[2, 4] = “102” and
substring str[4, 6] = “201” has equal number
of 0, 1 and 2 
Example 2:
Input: str = “11100022”
Output: 0
Explanation: There is no substring with
equal number of 0 , 1 and 2.
Your Task:  
You don't need to read input or print anything.Your task is to complete the function getSubstringWithEqual012() which takes a single string str as input and returns the answer.
Expected Time Complexity: O(N)
Expected Auxiliary Space: O(N)
Constraints:
1 ≤ N ≤ 10^{5}

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: String algorithms

Data structures

Starter code: #User function Template for python3



class Solution:



    def getSubstringWithEqual012(self, Str):

        # code here

Solutions:
class Solution:

	def getSubstringWithEqual012(self, Str):
		n = len(Str)
		hash_map = {(0, 0): 1}
		count = [0, 0, 0]
		result = 0
		for i in range(n):
			count[int(Str[i])] += 1
			temp = (count[0] - count[1], count[1] - count[2])
			if temp in hash_map:
				result += hash_map[temp]
				hash_map[temp] += 1
			else:
				hash_map[temp] = 1
		return result


class Solution:

	def getSubstringWithEqual012(self, s):
		c0 = 0
		c1 = 0
		c2 = 0
		dic = {}
		ans = 0
		x = '0@0'
		dic[x] = 1
		for i in range(len(s)):
			if s[i] == '1':
				c1 += 1
			elif s[i] == '2':
				c2 += 1
			else:
				c0 += 1
			x = str(c0 - c1) + '@' + str(c1 - c2)
			if x not in dic:
				dic[x] = 1
			else:
				ans += dic[x]
				dic[x] += 1
		return ans


class Solution:

	def solve(self, arr, n):
		z1 = 0
		z0 = 0
		z2 = 0
		d = {}
		d[0, 0] = 1
		ans = 0
		for i in range(n):
			if arr[i] == '0':
				z0 += 1
			elif arr[i] == '1':
				z1 += 1
			else:
				z2 += 1
			temp = (z0 - z1, z0 - z2)
			if temp not in d:
				d[temp] = 1
			else:
				ans += d[temp]
				d[temp] += 1
		return ans

	def getSubstringWithEqual012(self, Str):
		return self.solve(Str, len(Str))


class Solution:

	def getSubstringWithEqual012(self, string):
		N = len(string)
		mp = dict()
		mp[0, 0] = 1
		(zc, oc, tc) = (0, 0, 0)
		res = 0
		for i in range(N):
			if string[i] == '0':
				zc += 1
			elif string[i] == '1':
				oc += 1
			else:
				tc += 1
			tmp = (zc - oc, zc - tc)
			if tmp not in mp:
				res += 0
			else:
				res += mp[tmp]
			if tmp in mp:
				mp[tmp] += 1
			else:
				mp[tmp] = 1
		return res


class Solution:

	def getSubstringWithEqual012(self, Str):
		hashMap = {'0#0': 1}
		twos = ones = zeros = 0
		count = 0
		for r in range(len(Str)):
			if Str[r] == '2':
				twos += 1
			elif Str[r] == '1':
				ones += 1
			else:
				zeros += 1
			dif = str(twos - ones) + '#' + str(ones - zeros)
			if dif in hashMap:
				count += hashMap[dif]
			hashMap[dif] = hashMap.get(dif, 0) + 1
		return count


class Solution:

	def getSubstringWithEqual012(self, Str):
		z = 0
		o = 0
		t = 0
		u = {}
		count = 0
		for i in Str:
			if i == '0':
				z += 1
			elif i == '1':
				o += 1
			elif i == '2':
				t += 1
			if z == o and o == t:
				count += 1
			key = (z - o, o - t)
			if key in u:
				count += u[key]
			u[key] = u.get(key, 0) + 1
		return count


class Solution:

	def getSubstringWithEqual012(self, s):
		dict = {'0#0': 0}
		(c0, c1, c2) = (0, 0, 0)
		for i in range(len(s)):
			if s[i] == '0':
				c0 += 1
			elif s[i] == '1':
				c1 += 1
			else:
				c2 += 1
			val = str(c1 - c0) + '#' + str(c2 - c1)
			dict[val] = 0 if val not in dict else dict[val] + 1
		count = 0
		for num in dict:
			count += dict[num] * (dict[num] + 1) // 2
		return count


from collections import defaultdict

class Solution:

	def getSubstringWithEqual012(self, Str):
		res = 0
		d = defaultdict()
		d[0, 0] = 1
		z = 0
		o = 0
		t = 0
		for i in Str:
			if i == '0':
				z += 1
			elif i == '1':
				o += 1
			else:
				t += 1
			k = z - o
			l = z - t
			if (k, l) not in d.keys():
				d[k, l] = 1
			else:
				res += d[k, l]
				d[k, l] += 1
		return res


class Solution:

	def getSubstringWithEqual012(self, Str):
		count = 0
		hashmap = {'0#0': 1}
		c0 = c1 = c2 = 0
		for n in Str:
			if n == '0':
				c0 += 1
			elif n == '1':
				c1 += 1
			else:
				c2 += 1
			k1 = c1 - c0
			k2 = c2 - c1
			fk = str(k1) + '#' + str(k2)
			if fk not in hashmap.keys():
				hashmap[fk] = 1
			else:
				count += hashmap[fk]
				hashmap[fk] += 1
		return count


class Solution:

	def getSubstringWithEqual012(self, Str):
		n = len(Str)
		zc = 0
		oc = 0
		tc = 0
		mp = dict()
		mp[0, 0] = 1
		res = 0
		for i in range(n):
			if Str[i] == '0':
				zc += 1
			elif Str[i] == '1':
				oc += 1
			elif Str[i] == '2':
				tc += 1
			tmp = (zc - oc, zc - tc)
			if tmp in mp:
				res += mp[tmp]
				mp[tmp] += 1
			else:
				mp[tmp] = 1
		return res


class Solution:

	def getSubstringWithEqual012(self, s):
		d = {}
		(z, o, t) = (0, 0, 0)
		d[0, 0] = 1
		count = 0
		n = len(s)
		for i in range(n):
			if s[i] == '0':
				z += 1
			elif s[i] == '1':
				o += 1
			else:
				t += 1
			dif = (z - o, z - t)
			if dif in d.keys():
				count += d[dif]
			d[dif] = d.get(dif, 0) + 1
		return count


from collections import defaultdict

class Solution:

	def getSubstringWithEqual012(self, s):
		store = defaultdict(lambda : 0)
		store[0, 0, 0] += 1
		count = 0
		zers = 0
		ones = 0
		twos = 0
		for item in s:
			zers += item == '0'
			ones += item == '1'
			twos += item == '2'
			if zers and ones and twos:
				zers -= 1
				ones -= 1
				twos -= 1
			count += store[zers, ones, twos]
			store[zers, ones, twos] += 1
		return count


class Solution:

	def getSubstringWithEqual012(self, Str):
		a = 0
		b = 0
		c = 0
		d = {}
		d[0, 0] = 1
		ans = 0
		for i in Str:
			if i == '0':
				a += 1
			elif i == '1':
				b += 1
			else:
				c += 1
			temp = (a - b, a - c)
			if temp in d:
				ans += d[temp]
				d[temp] += 1
			else:
				d[temp] = 1
		return ans


class Solution:

	def getSubstringWithEqual012(self, Str):
		(count0, count1, count2) = (0, 0, 0)
		freq = {(0, 0): 1}
		ans = 0
		for c in Str:
			if c == '0':
				count0 += 1
			elif c == '1':
				count1 += 1
			else:
				count2 += 1
			key = (count0 - count1, count0 - count2)
			if key in freq:
				ans += freq[key]
				freq[key] += 1
			else:
				freq[key] = 1
		return ans


class Solution:

	def getSubstringWithEqual012(self, Str):
		f0 = 0
		f1 = 0
		f2 = 0
		memo = {'0#0': 1}
		ans = 0
		for acquire in range(0, len(Str)):
			character = Str[acquire]
			if character == '0':
				f0 += 1
			elif character == '1':
				f1 += 1
			elif character == '2':
				f2 += 1
			exp = str(f1 - f0) + '#' + str(f2 - f1)
			if exp in memo:
				ans += memo[exp]
				memo[exp] += 1
			else:
				memo[exp] = 1
		return ans


class Solution:

	def getSubstringWithEqual012(self, Str):
		z = dict()
		(z['0'], z['1'], z['2']) = (0, 0, 0)
		d = dict()
		ans = 0
		d['0#0'] = 1
		for i in Str:
			z[i] += 1
			temp = str(z['1'] - z['0']) + '#' + str(z['2'] - z['1'])
			if temp in d:
				ans += d[temp]
				d[temp] += 1
			else:
				d[temp] = 1
		return ans


class Solution:

	def getSubstringWithEqual012(self, Str):
		(c0, c1, c2) = (0, 0, 0)
		hashmap = {(0, 0): 1}
		ans = 0
		for i in range(len(Str)):
			if Str[i] == '0':
				c0 += 1
			elif Str[i] == '1':
				c1 += 1
			else:
				c2 += 1
			key = (c0 - c1, c0 - c2)
			if key in hashmap:
				ans += hashmap[key]
				hashmap[key] += 1
			else:
				hashmap[key] = 1
		return ans


class Solution:

	def getSubstringWithEqual012(self, Str):
		count0 = count1 = count2 = 0
		(ans, key) = (0, '0#0')
		hm = dict()
		hm[key] = 1
		for ch in Str:
			if ch == '0':
				count0 += 1
			if ch == '1':
				count1 += 1
			if ch == '2':
				count2 += 1
			key = str(count1 - count0) + '#' + str(count2 - count1)
			if key in hm:
				ans += hm[key]
				hm[key] += 1
			else:
				hm[key] = 1
		return ans


class Solution:

	def getSubstringWithEqual012(self, s):
		n = len(s)
		d = {}
		d[0, 0] = 1
		(c_0, c_1, c_2) = (0, 0, 0)
		ans = 0
		for i in s:
			if i == '0':
				c_0 += 1
			elif i == '1':
				c_1 += 1
			else:
				c_2 += 1
			x = (c_0 - c_1, c_0 - c_2)
			if x in d:
				ans += d[x]
			d[x] = d.get(x, 0) + 1
		return ans


from collections import Counter

class Solution:

	def getSubstringWithEqual012(self, Str):
		hashtable = Counter({(0, 0): 1})
		zero = one = two = 0
		ans = 0
		for ch in Str:
			if ch == '0':
				zero += 1
			elif ch == '1':
				one += 1
			else:
				two += 1
			current_difference = (zero - one, zero - two)
			if current_difference in hashtable:
				ans += hashtable[current_difference]
			hashtable[current_difference] += 1
		return ans


class Solution:

	def getSubstringWithEqual012(self, Str):
		Count = 0
		memo = {}
		C0 = C1 = C2 = 0
		key = str(C1 - C0) + '#' + str(C2 - C1)
		memo[key] = 1
		for i in range(len(Str)):
			if Str[i] == '0':
				C0 += 1
			elif Str[i] == '1':
				C1 += 1
			else:
				C2 += 1
			currentKey = str(C1 - C0) + '#' + str(C2 - C1)
			if currentKey in memo:
				Count += memo[currentKey]
				memo[currentKey] += 1
			else:
				memo[currentKey] = 1
		return Count


class Solution:

	def getSubstringWithEqual012(self, Str):
		hmap = {'0': 0, '1': 0, '2': 0}
		smap = {(0, 0): 0}
		n = len(Str)
		for i in range(n):
			hmap[Str[i]] += 1
			val = (hmap['2'] - hmap['1'], hmap['1'] - hmap['0'])
			if val not in smap:
				smap[val] = 0
			else:
				smap[val] += 1
		res = 0
		for key in smap:
			m = smap[key]
			res += m * (m + 1) // 2
		return res


class Solution:

	def getSubstringWithEqual012(self, Str):
		answer = 0
		memo = {}
		cz = c1 = c2 = 0
		key = str(c1 - cz) + '#' + str(c2 - c1)
		memo[key] = 1
		for i in range(len(Str)):
			if Str[i] == '0':
				cz += 1
			elif Str[i] == '1':
				c1 += 1
			else:
				c2 += 1
			currentkey = str(c1 - cz) + '#' + str(c2 - c1)
			if currentkey in memo:
				answer += memo.get(currentkey)
				memo[currentkey] += 1
			else:
				memo[currentkey] = 1
		return answer


class Solution:

	def getSubstringWithEqual012(self, s):
		ans = 0
		z0 = 0
		z1 = 0
		z2 = 0
		d = {}
		d[str(z1 - z0) + '#' + str(z2 - z1)] = 1
		for i in range(len(s)):
			if s[i] == '0':
				z0 += 1
			elif s[i] == '1':
				z1 += 1
			else:
				z2 += 1
			ans3 = str(z1 - z0) + '#' + str(z2 - z1)
			if ans3 in d:
				ans += d[ans3]
				d[ans3] += 1
			else:
				d[ans3] = 1
		return ans


class Solution:

	def getSubstringWithEqual012(self, Str):
		(zc, oc, tc, res) = (0, 0, 0, 0)
		mp = dict()
		mp[0, 0] = 1
		for i in range(len(Str)):
			if Str[i] == '0':
				zc += 1
			elif Str[i] == '1':
				oc += 1
			else:
				tc += 1
			temp = (zc - oc, zc - tc)
			if temp not in mp:
				res += 0
			else:
				res += mp[temp]
			if temp in mp:
				mp[temp] += 1
			else:
				mp[temp] = 1
		return res


class Solution:

	def getSubstringWithEqual012(self, Str):
		l = 0
		r = 0
		n = len(Str)
		if n <= 2:
			return 0
		count0 = 0
		count1 = 0
		count2 = 0
		res = 0
		dict1 = {}
		dict1[0, 0] = 1
		for i in range(n):
			if Str[i] == '0':
				count0 += 1
			elif Str[i] == '1':
				count1 += 1
			else:
				count2 += 1
			temp = (count0 - count1, count0 - count2)
			if temp in dict1:
				res += dict1[temp]
				dict1[temp] += 1
			else:
				dict1[temp] = 1
		return res


class Solution:

	def getSubstringWithEqual012(self, Str):
		count0 = 0
		count1 = 0
		count2 = 0
		delta10 = count1 - count0
		delta21 = count2 - count1
		mp = {}
		key = (delta10, delta21)
		mp[key] = 1
		res = 0
		for i in range(len(Str)):
			if Str[i] == '0':
				count0 += 1
			elif Str[i] == '1':
				count1 += 1
			elif Str[i] == '2':
				count2 += 1
			delta10 = count1 - count0
			delta21 = count2 - count1
			key = (delta10, delta21)
			if key in mp:
				res += mp[key]
				mp[key] += 1
			else:
				mp[key] = 1
		return res


import collections

class Solution:

	def getSubstringWithEqual012(self, Str):
		tmp = dict()
		tmp[0, 0] = 1
		res = 0
		(z, o, t) = (0, 0, 0)
		for ch in Str:
			if ch == '0':
				z += 1
			elif ch == '1':
				o += 1
			else:
				t += 1
			delta = (z - o, t - o)
			if delta in tmp:
				res += tmp[delta]
				tmp[delta] += 1
			else:
				tmp[delta] = 1
		return res


class Solution:

	def getSubstringWithEqual012(self, Str):
		ans = 0
		z0 = 0
		z1 = 0
		z2 = 0
		m = {}
		k1 = z0 - z1
		k2 = z1 - z2
		key = str(k1) + '-' + str(k2)
		m[key] = 1
		for i in range(len(Str)):
			if Str[i] == '0':
				z0 += 1
			elif Str[i] == '1':
				z1 += 1
			elif Str[i] == '2':
				z2 += 1
			k1 = z0 - z1
			k2 = z1 - z2
			key = str(k1) + '-' + str(k2)
			if key in m:
				ans += m[key]
				m[key] += 1
			else:
				m[key] = 1
		return ans


class Solution:

	def getSubstringWithEqual012(self, Str):
		arr = Str
		ans = 0
		hashmap = {}
		count0 = 0
		count1 = 0
		count2 = 0
		delta1 = count1 - count0
		delta2 = count2 - count1
		key = str(delta2) + '#' + str(delta1)
		hashmap[key] = 1
		for i in range(len(arr)):
			if arr[i] == '0':
				count0 += 1
			if arr[i] == '1':
				count1 += 1
			if arr[i] == '2':
				count2 += 1
			delta1 = count1 - count0
			delta2 = count2 - count1
			key = str(delta2) + '#' + str(delta1)
			if hashmap.get(key) != None:
				ans += hashmap[key]
				hashmap[key] += 1
			if hashmap.get(key) == None:
				hashmap[key] = 1
		return ans


class Solution:

	def getSubstringWithEqual012(self, Str):
		N = len(Str)
		mp = dict()
		mp[0, 0] = 1
		(zc, oc, tc) = (0, 0, 0)
		ans = 0
		for i in range(N):
			if Str[i] == '0':
				zc += 1
			if Str[i] == '1':
				oc += 1
			if Str[i] == '2':
				tc += 1
			tmp = (zc - oc, zc - tc)
			if tmp in mp:
				ans += mp[tmp]
				mp[tmp] += 1
			else:
				mp[tmp] = 1
		return ans


class Solution:

	def getSubstringWithEqual012(self, Str):
		hashmap = {}
		countZero = countOne = countTwo = 0
		ans = 0
		hashmap[str(countOne - countZero) + '#' + str(countTwo - countOne)] = 1
		for i in range(len(Str)):
			if Str[i] == '0':
				countZero += 1
			elif Str[i] == '1':
				countOne += 1
			else:
				countTwo += 1
			curr = str(countOne - countZero) + '#' + str(countTwo - countOne)
			if curr in hashmap:
				ans += hashmap[curr]
				hashmap[curr] += 1
			else:
				hashmap[curr] = 1
		return ans


class Solution:

	def getSubstringWithEqual012(self, Str):
		c0 = 0
		c1 = 0
		c2 = 0
		hmap = {'0#0': 1}
		ans = 0
		for ch in Str:
			if ch == '0':
				c0 += 1
			elif ch == '1':
				c1 += 1
			else:
				c2 += 1
			key = str(c1 - c0) + '#' + str(c2 - c1)
			ans += hmap.get(key, 0)
			hmap[key] = hmap.get(key, 0) + 1
		return ans


class Solution:

	def getSubstringWithEqual012(self, S):
		my_dic = {(0, 0): 1}
		(z_c, o_c, t_c, count) = (0, 0, 0, 0)
		for i in range(len(S)):
			if S[i] == '0':
				z_c += 1
			elif S[i] == '1':
				o_c += 1
			else:
				t_c += 1
			temp = (z_c - o_c, z_c - t_c)
			if temp not in my_dic:
				count += 0
			else:
				count += my_dic[temp]
			if temp in my_dic:
				my_dic[temp] += 1
			else:
				my_dic[temp] = 1
		return count


class Solution:

	def getSubstringWithEqual012(self, s):
		(a, b, c) = (0, 0, 0)
		has = {(0, 0): 1}
		res = 0
		for i in range(len(s)):
			if s[i] == '0':
				a += 1
			elif s[i] == '1':
				b += 1
			else:
				c += 1
			x = (b - a, c - b)
			if x in has:
				res += has[x]
				has[x] += 1
			else:
				has[x] = 1
		return res


class Solution:

	def getSubstringWithEqual012(self, Str):
		memo = {}
		answer = 0
		z0 = 0
		z1 = 0
		z2 = 0
		mKey = str(z1 - z0) + '#' + str(z2 - z1)
		memo[mKey] = 1
		for acquire in range(len(Str)):
			currentVal = Str[acquire]
			if currentVal == '0':
				z0 += 1
			if currentVal == '1':
				z1 += 1
			if currentVal == '2':
				z2 += 1
			mKey = str(z1 - z0) + '#' + str(z2 - z1)
			if mKey in memo:
				answer += memo[mKey]
				memo[mKey] += 1
			else:
				memo[mKey] = 1
		return answer


class Solution:

	def getSubstringWithEqual012(self, Str):
		z0 = 0
		z1 = 0
		z2 = 0
		d = {}
		d[0, 0] = 1
		ans = 0
		for num in Str:
			if num == '0':
				z0 = z0 + 1
			elif num == '1':
				z1 = z1 + 1
			else:
				z2 = z2 + 1
			temp = (z0 - z1, z2 - z1)
			if temp not in d:
				d[temp] = 1
			else:
				ans = ans + d[temp]
				d[temp] = d[temp] + 1
		return ans


class Solution:

	def getSubstringWithEqual012(self, Str):
		(a, b, c) = (0, 0, 0)
		res = 0
		dict = {}
		dict[0, 0] = 1
		for i in range(len(Str)):
			if Str[i] == '0':
				a += 1
			if Str[i] == '1':
				b += 1
			if Str[i] == '2':
				c += 1
			z = (b - a, c - b)
			if z in dict:
				res += dict[z]
				dict[z] += 1
			else:
				dict[z] = 1
		return res


class Solution:

	def getSubstringWithEqual012(self, s):
		tmp = {}
		tmp[0, 0] = 1
		n = len(s)
		res = 0
		(c0, c1, c2) = (0, 0, 0)
		for i in range(n):
			if s[i] == '0':
				c0 += 1
			if s[i] == '1':
				c1 += 1
			if s[i] == '2':
				c2 += 1
			d1 = c1 - c0
			d2 = c2 - c0
			if (d1, d2) in tmp:
				res += tmp[d1, d2]
				tmp[d1, d2] += 1
			else:
				tmp[d1, d2] = 1
		return res


class Solution:

	def getSubstringWithEqual012(self, Str):
		(z0, z1, z2) = (0, 0, 0)
		expHash = {}
		exp = str(z0 - z1) + '-' + str(z2 - z1)
		expHash[exp] = 1
		count = 0
		for num in Str:
			if num == '0':
				z0 += 1
			elif num == '1':
				z1 += 1
			else:
				z2 += 1
			cur_exp = str(z1 - z0) + '-' + str(z2 - z1)
			if cur_exp in expHash:
				count += expHash[cur_exp]
				expHash[cur_exp] += 1
			else:
				expHash[cur_exp] = 1
		return count


class Solution:

	def getSubstringWithEqual012(self, s):
		d = {(0, 0): 1}
		z = 0
		o = 0
		t = 0
		res = 0
		n = len(s)
		for i in range(n):
			if s[i] == '0':
				z += 1
			elif s[i] == '1':
				o += 1
			else:
				t += 1
			te = (z - o, z - t)
			if te in d:
				res += d[te]
				d[te] += 1
			else:
				d[te] = 1
		return res


class Solution:

	def getSubstringWithEqual012(self, Str):
		count = {}
		count['0'] = 0
		count['1'] = 0
		count['2'] = 0
		ans = 0
		dictt = {'0#0': 1}
		for i in range(len(Str)):
			count[Str[i]] += 1
			diff1 = count['1'] - count['0']
			diff2 = count['2'] - count['1']
			key = str(diff1) + '#' + str(diff2)
			if key in dictt:
				ans += dictt[key]
				dictt[key] += 1
			else:
				dictt[key] = 1
		return ans


class Solution:

	def getSubstringWithEqual012(self, Str):
		count0s = count1s = count2s = 0
		memo = {'0#0': 1}
		ans = 0
		for (i, num) in enumerate(Str):
			if num == '0':
				count0s += 1
			elif num == '1':
				count1s += 1
			else:
				count2s += 1
			currKey = str(count2s - count1s) + '#' + str(count1s - count0s)
			if currKey in memo:
				ans += memo[currKey]
				memo[currKey] += 1
			else:
				memo[currKey] = 1
		return ans


class Solution:

	def getSubstringWithEqual012(self, Str):
		z = 0
		o = 0
		t = 0
		i = 0
		count = 0
		dict = {'0#0': 1}
		while i < len(Str):
			if Str[i] == '0':
				z += 1
			elif Str[i] == '1':
				o += 1
			else:
				t += 1
			temp = str(o - z) + '#' + str(t - o)
			if dict.get(temp):
				count += dict.get(temp)
				dict[temp] += 1
			else:
				dict[temp] = 1
			i += 1
		if z == 1 and o == 1 and (t == 1):
			return 1
		return count


class Solution:

	def getSubstringWithEqual012(self, Str):
		z1 = 0
		z0 = 0
		z2 = 0
		d = {}
		d[0, 0] = 1
		ans = 0
		for i in range(len(Str)):
			if Str[i] == '0':
				z0 += 1
			elif Str[i] == '1':
				z1 += 1
			else:
				z2 += 1
			temp = (z0 - z1, z0 - z2)
			if temp not in d:
				d[temp] = 1
			else:
				ans += d[temp]
				d[temp] += 1
		return ans
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		Str = input()
		solObj = Solution()
		print(solObj.getSubstringWithEqual012(Str))


class Solution:

	def getSubstringWithEqual012(self, stri):
		n = len(stri)
		mp = dict()
		mp[0, 0] = 1
		(zc, oc, tc) = (0, 0, 0)
		res = 0
		for i in range(n):
			if stri[i] == '0':
				zc += 1
			elif stri[i] == '1':
				oc += 1
			else:
				tc += 1
			tmp = (zc - oc, zc - tc)
			if tmp not in mp:
				res += 0
			else:
				res += mp[tmp]
			if tmp in mp:
				mp[tmp] += 1
			else:
				mp[tmp] = 1
		return res
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		Str = input()
		solObj = Solution()
		print(solObj.getSubstringWithEqual012(Str))


class Solution:

	def getSubstringWithEqual012(self, Str):
		s = Str
		n = len(s)
		count_z = 0
		count_o = 0
		count_t = 0
		result = 0
		d = dict()
		d[0, 0] = 1
		for i in range(n):
			if s[i] == '0':
				count_z += 1
			elif s[i] == '1':
				count_o += 1
			else:
				count_t += 1
			diff = (count_z - count_o, count_z - count_t)
			if diff in d:
				result += d[diff]
			else:
				result += 0
			if diff in d:
				d[diff] += 1
			else:
				d[diff] = 1
		return result
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		Str = input()
		solObj = Solution()
		print(solObj.getSubstringWithEqual012(Str))


class Solution:

	def getSubstringWithEqual012(self, Str):
		count1 = count2 = count0 = count = 0
		temp = str(count1 - count0) + '#' + str(count2 - count1)
		memo = {temp: 1}
		for (i, num) in enumerate(Str):
			if num == '0':
				count0 += 1
			elif num == '1':
				count1 += 1
			else:
				count2 += 1
			currkey = str(count1 - count0) + '#' + str(count2 - count1)
			if currkey in memo:
				count += memo[currkey]
				memo[currkey] += 1
			else:
				memo[currkey] = 1
		return count
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		Str = input()
		solObj = Solution()
		print(solObj.getSubstringWithEqual012(Str))


class Solution:

	def getSubstringWithEqual012(self, Str):
		d = {'0#0': 1}
		c0 = 0
		c1 = 0
		c2 = 0
		output = 0
		s = Str
		for i in range(len(Str)):
			if s[i] == '0':
				c0 += 1
			elif s[i] == '1':
				c1 += 1
			else:
				c2 += 1
			d10 = c0 - c1
			d12 = c1 - c2
			temp = str(d10) + '#' + str(d12)
			if temp not in d:
				d[temp] = 1
			else:
				output += d[temp]
				d[temp] += 1
		return output
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		Str = input()
		solObj = Solution()
		print(solObj.getSubstringWithEqual012(Str))


class Solution:

	def getSubstringWithEqual012(self, Str):
		dict = {'0#0': 1}
		ans = 0
		c0 = 0
		c2 = 0
		c1 = 0
		for i in Str:
			if i == '0':
				c0 += 1
			elif i == '1':
				c1 += 1
			else:
				c2 += 1
			key = str(c1 - c0) + '#' + str(c2 - c1)
			if dict.get(key):
				ans += dict.get(key)
				dict[key] += 1
			else:
				dict.update({key: 1})
		if c0 == 1 and c2 == 1 and (c1 == 1):
			return 1
		return ans
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		Str = input()
		solObj = Solution()
		print(solObj.getSubstringWithEqual012(Str))


class Solution:

	def getSubstringWithEqual012(self, Str):
		a = b = c = ans = 0
		d = {}
		d[0, 0] = 1
		for i in range(len(Str)):
			if Str[i] == '0':
				a += 1
			elif Str[i] == '1':
				b += 1
			elif Str[i] == '2':
				c += 1
			temp = (a - b, a - c)
			if temp not in d:
				d[temp] = 1
			else:
				ans += d[temp]
				d[temp] += 1
		return ans


class Solution:

	def getSubstringWithEqual012(self, s):
		(ans, z0, z1, z2) = (0, 0, 0, 0)
		memo = {}
		memo[0, 0] = 1
		for i in range(len(s)):
			if s[i] == '0':
				z0 += 1
			elif s[i] == '1':
				z1 += 1
			else:
				z2 += 1
			expr = (z1 - z0, z2 - z1)
			if expr in memo:
				ans += memo[expr]
				memo[expr] += 1
			else:
				memo[expr] = 1
		return ans


class Solution:

	def getSubstringWithEqual012(self, Str):
		ht = {}
		ht['0#0'] = 1
		zero_count = 0
		one_count = 0
		two_count = 0
		ans = 0
		for ch in Str:
			if ch == '2':
				two_count += 1
			elif ch == '1':
				one_count += 1
			else:
				zero_count += 1
			key = str(one_count - zero_count) + '#' + str(two_count - one_count)
			if key in ht:
				ans += ht[key]
				ht[key] += 1
			else:
				ht[key] = 1
		return ans


class Solution:

	def getSubstringWithEqual012(self, Str):
		n = len(Str)
		z1 = 0
		z0 = 0
		z2 = 0
		d = {}
		d[0, 0] = 1
		ans = 0
		for i in range(n):
			if Str[i] == '0':
				z0 += 1
			elif Str[i] == '1':
				z1 += 1
			else:
				z2 += 1
			temp = (z0 - z1, z0 - z2)
			if temp not in d:
				d[temp] = 1
			else:
				ans += d[temp]
				d[temp] += 1
		return ans
		n = len(Str)
		mp = dict()
		mp[0, 0] = 1
		(zc, oc, tc) = (0, 0, 0)
		res = 0
		for i in range(n):
			if Str[i] == '0':
				zc += 1
			elif Str[i] == '1':
				oc += 1
			else:
				tc += 1
			tmp = (zc - oc, zc - tc)
			if tmp not in mp:
				res += 0
			else:
				res += mp[tmp]
			if tmp in mp:
				mp[tmp] += 1
			else:
				mp[tmp] = 1
		return res


class Solution:

	def getSubstringWithEqual012(self, Str):
		cz = 0
		co = 0
		ct = 0
		n = len(Str)
		map1 = {}
		map1[0, 0] = 1
		res = 0
		for i in range(len(Str)):
			if Str[i] == '0':
				cz += 1
			elif Str[i] == '1':
				co += 1
			else:
				ct += 1
			temp = (co - cz, ct - co)
			if temp in map1:
				res += map1[temp]
				map1[temp] += 1
			else:
				map1[temp] = 1
		return res


class Solution:

	def getSubstringWithEqual012(self, Str):
		count0 = 0
		count1 = 0
		count2 = 0
		key = str(0) + '#' + str(0)
		m = {}
		ans = 0
		m[key] = 1
		for i in Str:
			if i == '0':
				count0 += 1
			elif i == '1':
				count1 += 1
			else:
				count2 += 1
			key = str(count1 - count0) + '#' + str(count2 - count1)
			if key in m:
				ans += m[key]
				m[key] += 1
			else:
				m[key] = 1
		return ans


class Solution:

	def getSubstringWithEqual012(self, Str):
		z0 = 0
		z1 = 0
		z2 = 0
		totalSubStrCount = 0
		firstDiff = z1 - z0
		secondDiff = z2 - z1
		currKey = str(firstDiff) + '#' + str(secondDiff)
		memo = {}
		memo[currKey] = 1
		for index in range(0, len(Str)):
			currNumber = Str[index]
			if currNumber == '0':
				z0 += 1
			elif currNumber == '1':
				z1 += 1
			else:
				z2 += 1
			firstDiff = z1 - z0
			secondDiff = z2 - z1
			currKey = str(firstDiff) + '#' + str(secondDiff)
			if memo.get(currKey) != None:
				totalSubStrCount += memo.get(currKey)
				memo[currKey] += 1
			else:
				memo[currKey] = 1
		return totalSubStrCount


class Solution:

	def getSubstringWithEqual012(self, Str):
		m = {(0, 0): 1}
		coz = 0
		coo = 0
		cot = 0
		ans = 0
		for i in Str:
			if i == '1':
				coo += 1
			elif i == '0':
				coz += 1
			else:
				cot += 1
			dot = coo - cot
			doz = coo - coz
			a = (dot, doz)
			if a in m:
				ans += m[a]
				m[a] = m[a] + 1
			else:
				m[a] = 1
		return ans


class Solution:

	def getSubstringWithEqual012(self, Str):
		cnt0 = 0
		cnt1 = 0
		cnt2 = 0
		h = {}
		ans = 0
		key = '0#0'
		h[key] = 1
		for item in Str:
			if item == '0':
				cnt0 += 1
			elif item == '1':
				cnt1 += 1
			else:
				cnt2 += 1
			key = '{}#{}'.format(cnt1 - cnt0, cnt2 - cnt1)
			if key in h:
				ans += h[key]
				h[key] += 1
			else:
				h[key] = 1
		return ans


class Solution:

	def getSubstringWithEqual012(self, Str):
		result = 0
		(prefix_sum_0, prefix_sum_1, prefix_sum_2) = (0, 0, 0)
		ap = {}
		ap[0, 0] = 1
		for i in range(len(Str)):
			if Str[i] == '0':
				prefix_sum_0 += 1
			elif Str[i] == '1':
				prefix_sum_1 += 1
			else:
				prefix_sum_2 += 1
			difference_pair = (prefix_sum_0 - prefix_sum_1, prefix_sum_1 - prefix_sum_2)
			if difference_pair in ap.keys():
				result += ap[difference_pair]
				ap[difference_pair] += 1
			else:
				ap[difference_pair] = 1
		return result


class Solution:

	def getSubstringWithEqual012(self, Str):
		ap = {}
		ap[0, 0] = 1
		ans = 0
		(a, b, c) = (0, 0, 0)
		for i in range(len(Str)):
			if Str[i] == '0':
				a += 1
			elif Str[i] == '1':
				b += 1
			else:
				c += 1
			kp = (b - a, c - b)
			if kp in ap.keys():
				ans += ap[kp]
				ap[kp] += 1
			else:
				ap[kp] = 1
		return ans