Given string s consisting only a,b,c. return the number of substrings containing at least one occurrence of all these characters a, b, and c.
Example 1:
Input:
abcabc
Output:
10
Explanation:
The required substrings  are "abc", "abca", "abcab", "abcabc",
"bca", "bcab", "bcabc", "cab", "cabc" and "abc".
Example 2:
Input:
aaacb
Output:
3
Your Task:
You don't have to read input or print anything. Your task is to complete the function countSubstring() which takes the string s and returns the count of substring having at least a,b,c.
Expected Time Complexity: O(n)
Expected Space Complexity: O(1)
Constraint:
3<=s.length<=5 x 10^{4  }
S only contains a,b,c.

Source: geeksforgeeks | Difficulty: MEDIUM

Starter code: #User function Template for python3



class Solution:

    def countSubstring(self, s):

        # Code here

Solutions:
class Solution:

	def countSubstring(self, s):
		n = len(s)
		j = 0
		(a, b, c) = (0, 0, 0)
		ans = 0
		for i in range(n):
			if s[i] == 'a':
				a += 1
			elif s[i] == 'b':
				b += 1
			else:
				c += 1
			while a > 0 and b > 0 and (c > 0):
				ans += n - i
				if s[j] == 'a':
					a -= 1
				elif s[j] == 'b':
					b -= 1
				else:
					c -= 1
				j += 1
		return ans


class Solution:

	def countSubstring(self, s):
		ans = 0
		j = 0
		dic = {}
		for i in range(len(s)):
			el = s[i]
			if el in dic:
				dic[el] += 1
			else:
				dic[el] = 1
			if len(dic) == 3:
				while j < i:
					if dic['a'] == 0 or dic['b'] == 0 or dic['c'] == 0:
						break
					dic[s[j]] -= 1
					j += 1
				ans += j
		return ans


class Solution:

	def countSubstring(self, s):
		n = len(s)
		count = 0
		left = 0
		distinct = 0
		a = 0
		b = 0
		c = 0
		for i in range(n):
			right = i
			if s[i] == 'a':
				a += 1
			elif s[i] == 'b':
				b += 1
			elif s[i] == 'c':
				c += 1
			if a >= 1 and b >= 1 and (c >= 1):
				while a >= 1 and b >= 1 and (c >= 1):
					if s[left] == 'a':
						a -= 1
						if a == 0:
							distinct -= 1
					elif s[left] == 'b':
						b -= 1
						if b == 0:
							distinct -= 1
					elif s[left] == 'c':
						c -= 1
						if c == 0:
							distinct -= 1
					count += n - right
					left += 1
		return count


class Solution:

	def countSubstring(self, s):
		(count, left) = (0, 0)
		map = {x: 0 for x in 'abc'}
		for right in range(0, len(s)):
			map[s[right]] += 1
			while map['a'] and map['b'] and map['c']:
				map[s[left]] -= 1
				left += 1
			count += left
		return count


class Solution:

	def countSubstring(self, s):
		n = len(s)
		l = 0
		r = 0
		ans = 0
		hm = {}
		while r < n:
			if s[r] in hm:
				hm[s[r]] += 1
			else:
				hm[s[r]] = 1
			while len(hm) == 3:
				ans += n - r
				hm[s[l]] -= 1
				if hm[s[l]] == 0:
					del hm[s[l]]
				l += 1
			r += 1
		return ans


class Solution:

	def countSubstring(self, s):
		ans = 0
		(ca, cb, cc) = (-1, -1, -1)
		for i in range(len(s)):
			if s[i] == 'a':
				ca = i
			elif s[i] == 'b':
				cb = i
			elif s[i] == 'c':
				cc = i
			ans += min(ca, cb, cc) + 1
		return ans


class Solution:

	def countSubstring(self, s):
		N = len(s)
		t = {}
		tmp = 0
		answer = 0
		i = 0
		for j in range(N):
			t[s[j]] = 1 + t.get(s[j], 0)
			if 'a' in t and 'b' in t and ('c' in t):
				tmp = 0
				while i <= j and 'a' in t and ('b' in t) and ('c' in t):
					t[s[i]] = -1 + t.get(s[i], 0)
					if t[s[i]] == 0:
						del t[s[i]]
					i += 1
			answer += i
		return answer


class Solution:

	def countSubstring(self, s):
		count = 0
		n = len(s)
		d = {}
		j = 0
		for i in range(n):
			if s[i] in d:
				d[s[i]] += 1
			else:
				d[s[i]] = 1
			if len(d) == 3:
				while j < n and len(d) == 3:
					count = count + (n - i)
					d[s[j]] -= 1
					if d[s[j]] == 0:
						del d[s[j]]
					j = j + 1
		return count


class Solution:

	def countSubstring(self, s):
		(l, r) = (0, 0)
		n = len(s)
		count_fr = {}
		res = 0
		while r < n:
			count_fr[s[r]] = 1 + count_fr.get(s[r], 0)
			while len(count_fr) == 3:
				res += n - r
				count_fr[s[l]] -= 1
				if count_fr.get(s[l], 0) == 0:
					del count_fr[s[l]]
				l += 1
			r += 1
		return res


class Solution:

	def countSubstring(self, s):
		i = 0
		j = 0
		n = len(s)
		count = 0
		a = 0
		b = 0
		c = 0
		while j < n:
			if s[j] == 'a':
				a += 1
			elif s[j] == 'b':
				b += 1
			elif s[j] == 'c':
				c += 1
			while a > 0 and b > 0 and (c > 0):
				count += n - j
				if s[i] == 'a':
					a -= 1
				elif s[i] == 'b':
					b -= 1
				elif s[i] == 'c':
					c -= 1
				i += 1
			j += 1
		return count


class Solution:

	def countSubstring(self, s):
		count = 0
		(i, j) = (0, 0)
		m = {'a': 0, 'b': 0, 'c': 0}
		while j < len(s):
			m[s[j]] += 1
			while m['a'] > 0 and m['b'] > 0 and (m['c'] > 0):
				m[s[i]] -= 1
				i += 1
			count += i
			j += 1
		return count


class Solution:

	def countSubstring(self, s):
		count = 0
		(a, b, c) = (-1, -1, -1)
		for (i, x) in enumerate(s):
			if x == 'a':
				a = i
			elif x == 'b':
				b = i
			else:
				c = i
			if i > 1:
				count += min([a, b, c]) + 1
		return count


class Solution:

	def countSubstring(self, s):
		ans = 0
		j = 0
		i = 0
		(a, b, c) = (0, 0, 0)
		while j < len(s):
			if s[j] == 'a':
				a += 1
			elif s[j] == 'b':
				b += 1
			else:
				c += 1
			while a > 0 and b > 0 and (c > 0):
				ans += len(s) - j
				if s[i] == 'a':
					a -= 1
				elif s[i] == 'b':
					b -= 1
				elif s[i] == 'c':
					c -= 1
				i += 1
			j += 1
		return ans


class Solution:

	def countSubstring(self, s):
		(l, r) = (0, 0)
		(a, b, c) = (0, 0, 0)
		count = 0
		while r < len(s):
			if s[r] == 'a':
				a += 1
			elif s[r] == 'b':
				b += 1
			elif s[r] == 'c':
				c += 1
			while a > 0 and b > 0 and (c > 0):
				count += len(s) - r
				if s[l] == 'a':
					a -= 1
				elif s[l] == 'b':
					b -= 1
				elif s[l] == 'c':
					c -= 1
				l += 1
			r += 1
		return count


class Solution:

	def countSubstring(self, s):
		N = len(s)

		def total(count):
			if count == 0:
				return 0
			res = 0
			i = 0
			c = 0
			d = {}
			for j in range(N):
				if s[j] not in d or d[s[j]] == 0:
					d[s[j]] = 1
					c += 1
				else:
					d[s[j]] += 1
				if c <= count:
					res += j - i + 1
				else:
					while i < N and i <= j and (c > count):
						d[s[i]] -= 1
						if d[s[i]] == 0:
							c -= 1
						i += 1
					res += j - i + 1
			return res
		return total(3) - total(2)


class Solution:

	def countSubstring(self, s):
		n = len(s)
		ans = 0
		(i, j) = (0, 0)
		(ca, cb, cc) = (0, 0, 0)
		while i < n:
			if s[i] == 'a':
				ca += 1
			elif s[i] == 'b':
				cb += 1
			elif s[i] == 'c':
				cc += 1
			while ca > 0 and cb > 0 and (cc > 0):
				ans += n - i
				if s[j] == 'a':
					ca -= 1
				elif s[j] == 'b':
					cb -= 1
				elif s[j] == 'c':
					cc -= 1
				j += 1
			i += 1
		return ans


class Solution:

	def countSubstring(self, s):
		n = len(s)
		idxA = -1
		idxB = -1
		idxC = -1
		res = 0
		for i in range(n):
			if s[i] == 'a':
				idxA = i
			elif s[i] == 'b':
				idxB = i
			elif s[i] == 'c':
				idxC = i
			res += min(idxA, idxB, idxC) + 1
		return res


class Solution:

	def countSubstring(self, s):
		seen = {'a': 0, 'b': 0, 'c': 0}
		i = j = 0
		count = 0
		n = len(s)
		while i + 3 <= n:
			if seen['a'] >= 1 and seen['b'] >= 1 and (seen['c'] >= 1):
				seen[s[i]] -= 1
				i += 1
				count += n - j + 1
			elif j <= n - 1:
				seen[s[j]] += 1
				j += 1
			else:
				break
		return count


class Solution:

	def countSubstring(self, ch):
		d = {'a': 0, 'b': 0, 'c': 0}
		s = ans = 0
		for i in ch:
			d[i] += 1
			while d['a'] and d['b'] and d['c']:
				d[ch[s]] -= 1
				s += 1
			ans += s
		return ans


class Solution:

	def countSubstring(self, s):
		n = len(s)
		l = res = 0
		dic = {'a': 0, 'b': 0, 'c': 0}
		for r in range(n):
			dic[s[r]] += 1
			isValid = True
			for key in dic:
				if dic[key] <= 0:
					isValid = False
			while isValid:
				res += n - r
				if s[l] == 'a':
					dic['a'] += -1
				elif s[l] == 'b':
					dic['b'] += -1
				elif s[l] == 'c':
					dic['c'] += -1
				l += 1
				isValid = True
				for key in dic:
					if dic[key] <= 0:
						isValid = False
		return res


from collections import defaultdict

class Solution:

	def countSubstring(self, s):
		count = defaultdict(int)
		result = 0
		j = 0
		for i in range(len(s)):
			count[s[i]] += 1
			while len(count) == 3:
				result += len(s) - i
				count[s[j]] -= 1
				if not count[s[j]]:
					count.pop(s[j])
				j += 1
		return result


class Solution:

	def countSubstring(self, s: str) -> int:
		idx = [-1] * 3
		res = 0
		for i in range(len(s)):
			idx[ord(s[i]) - ord('a')] = i
			res += min(idx) + 1
		return res


class Solution:

	def countSubstring(self, s):
		count = 0
		(ind_a, ind_b, ind_c) = (-1, -1, -1)
		for (i, x) in enumerate(s):
			if x == 'a':
				ind_a = i
			elif x == 'b':
				ind_b = i
			elif x == 'c':
				ind_c = i
			if i > 1:
				count += min(ind_a, ind_b, ind_c) + 1
		return count


class Solution:

	def countSubstring(self, s):
		(idx_a, idx_b, idx_c) = (-1, -1, -1)
		count = 0
		for (i, x) in enumerate(s):
			if x == 'a':
				idx_a = i
			elif x == 'b':
				idx_b = i
			elif x == 'c':
				idx_c = i
			if i > 1:
				count += min([idx_a, idx_b, idx_c]) + 1
		return count


class Solution:

	def countSubstring(self, s):
		n = len(s)
		d = {i: 0 for i in 'abc'}
		(i, j) = (0, 0)
		ans = 0
		while j < n:
			d[s[j]] += 1
			while d['a'] and d['b'] and d['c']:
				d[s[i]] -= 1
				i += 1
			ans += i
			j += 1
		return ans


class Solution:

	def countSubstring(self, s):
		sDict = {ch: 0 for ch in 'abc'}
		ans = 0
		left = 0
		n = len(s)
		for right in range(n):
			sDict[s[right]] += 1
			while sDict['a'] and sDict['b'] and sDict['c']:
				sDict[s[left]] -= 1
				left += 1
			ans += left
		return ans


class Solution:

	def countSubstring(self, s):
		m = {'a': 0, 'b': 1, 'c': 2}
		l = [-1] * 3
		res = 0
		c = 0
		for i in s:
			l[m[i]] = c
			res += min(l) + 1
			c += 1
		return res