You are given a string s, a split is called good if you can split s into 2 non-empty strings p and q where its concatenation is equal to s and the number of distinct letters in p and q are the same.
Return the number of good splits you can make in s.
 
Example 1:
Input: s = "aacaba"
Output: 2
Explanation: There are 5 ways to split "aacaba" and 2 of them are good. 
("a", "acaba") Left string and right string contains 1 and 3 different letters respectively.
("aa", "caba") Left string and right string contains 1 and 3 different letters respectively.
("aac", "aba") Left string and right string contains 2 and 2 different letters respectively (good split).
("aaca", "ba") Left string and right string contains 2 and 2 different letters respectively (good split).
("aacab", "a") Left string and right string contains 3 and 1 different letters respectively.

Example 2:
Input: s = "abcd"
Output: 1
Explanation: Split the string as follows ("ab", "cd").

Example 3:
Input: s = "aaaaa"
Output: 4
Explanation: All possible splits are good.
Example 4:
Input: s = "acbadbaada"
Output: 2

 
Constraints:

s contains only lowercase English letters.
1 <= s.length <= 10^5

Source: leetcode | Difficulty: MEDIUM
Tags: String algorithms

Bit manipulation

Dynamic programming

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

Solutions:
class Solution:

	def numSplits(self, s: str) -> int:
		left = [0] * len(s)
		unique = set()
		n_distinct = 0
		for (i, l) in enumerate(s):
			if l not in unique:
				unique.add(l)
				n_distinct += 1
			left[i] = n_distinct
		count = 0
		unique = set()
		n_distinct = 0
		for i in range(len(s) - 1, 0, -1):
			if s[i] not in unique:
				unique.add(s[i])
				n_distinct += 1
			if n_distinct == left[i - 1]:
				count += 1
		return count


class Solution:

	def numSplits(self, s: str) -> int:
		index_one = 0
		index_two = 0
		set_one = set()
		set_two = set()
		s_r = s[::-1]
		for i in range(len(s)):
			print((i, len(set(s[:i + 1])), len(set(s[i + 1:]))))
			if len(set(s[:i + 1])) == len(set(s[i + 1:])):
				index_one = i
				break
			else:
				set_one.add(s[i])
		for i in range(len(s_r)):
			print((i, len(set(s_r[:i + 1])), len(set(s_r[i + 1:]))))
			if len(set(s_r[:i + 1])) == len(set(s_r[i + 1:])):
				print(i)
				index_two = len(s) - i - 1
				break
			else:
				set_two.add(s_r[i])
		print((index_one, index_two))
		return index_two - index_one


from collections import Counter

class Solution:

	def numSplits(self, s: str) -> int:
		right = Counter(s)
		left = set()
		res = 0
		for i in range(len(s) - 1):
			left.add(s[i])
			right[s[i]] -= 1
			res += len(left) == sum((i > 0 for i in right.values()))
		return res


class Solution:

	def numSplits(self, s: str) -> int:

		def decorate(a, b):
			final = {1: defaultdict(int), 2: defaultdict(int)}
			(count1, count2) = (0, 0)
			for char in a:
				final[1][char] += 1
				if final[1][char] == 1:
					count1 += 1
			for char in b:
				final[2][char] += 1
				if final[2][char] == 1:
					count2 += 1
			return (final, count1, count2)
		split = None
		(count1, count2) = (0, 0)
		total = 0
		for point in range(1, len(s)):
			if split == None:
				(split, count1, count2) = decorate(s[:point], s[point:])
			else:
				split[1][s[point - 1]] += 1
				if split[1][s[point - 1]] == 1:
					count1 += 1
				split[2][s[point - 1]] -= 1
				if split[2][s[point - 1]] == 0:
					count2 -= 1
			if count1 == count2:
				total += 1
		return total


class Solution:

	def count_chars(self, s):
		count = {}
		for c in s:
			if c in count:
				count[c] += 1
			else:
				count[c] = 1
		return count

	def dict_decr(self, d, c):
		if c in d:
			d[c] -= 1
		if d[c] <= 0:
			del d[c]

	def numSplits(self, s: str) -> int:
		(left, right) = (s[0], s[1:])
		left_chars = set([left])
		right_chars = self.count_chars(right)
		num_splits = 0
		while right:
			if len(left_chars) == len(right_chars.keys()):
				num_splits += 1
			c = right[0]
			self.dict_decr(right_chars, c)
			left_chars.add(c)
			left += c
			right = right[1:]
		return num_splits


class Solution:

	def numSplits(self, s: str) -> int:
		count = 0
		left = set(s[:1])
		right = set(s[1:])
		if len(left) == len(right):
			count += 1
		k = 0
		for i in range(1, len(s)):
			if s[i] not in left:
				left.add(s[i])
			if s[i] not in s[i + 1:]:
				k += 1
			diff = len(left) - (len(right) - k)
			if diff == 0:
				count += 1
			elif diff > 0:
				break
		return count


from collections import Counter

class Solution:

	def numSplits(self, s: str) -> int:
		no = 0
		x = Counter(s)
		y = Counter()
		if len(list(x.keys())) == len(list(y.keys())):
			no += 1
		for i in range(0, len(s) - 1):
			x[s[i]] -= 1
			if x[s[i]] == 0:
				del x[s[i]]
			if s[i] in y:
				y[s[i]] += 1
			else:
				y[s[i]] = 1
			if len(list(x.keys())) == len(list(y.keys())):
				no += 1
		return no


from collections import Counter

class Solution:

	def numSplits(self, s: str) -> int:
		num_splits = 0
		left = Counter()
		right = Counter(s)
		for char in s:
			left.update(char)
			right.subtract(char)
			if right[char] == 0:
				del right[char]
			if len(left) == len(right):
				num_splits += 1
		return num_splits


class Solution:

	def numSplits(self, s: str) -> int:
		pre = [0] * len(s)
		acc = set()
		cnt = 0
		for i in range(len(s) - 1):
			if s[i] not in acc:
				cnt += 1
				acc.add(s[i])
			pre[i] = cnt
		cnt = 0
		acc.clear()
		res = 0
		for i in range(len(s) - 1, 0, -1):
			if s[i] not in acc:
				cnt += 1
				acc.add(s[i])
			if pre[i - 1] == cnt:
				res += 1
		return res


class Solution:

	def numSplits(self, s: str) -> int:
		l_count = []
		r_count = []
		tmp = 0
		for i in range(len(s)):
			if s[i] not in s[:i]:
				tmp += 1
			l_count.append(tmp)
		tmp = 0
		for i in range(len(s))[::-1]:
			if s[i] not in s[i + 1:]:
				tmp += 1
			r_count.append(tmp)
		r_count = r_count[::-1]
		count = 0
		for i in range(len(r_count) - 1):
			if l_count[i] == r_count[i + 1]:
				count += 1
		return count


class Solution:

	def numSplits(self, s: str) -> int:
		n = len(s)
		output = 0
		dic = {}
		for (i, x) in enumerate(s):
			if not x in dic:
				dic[x] = [i, i]
			else:
				dic[x][1] = i
		for i in range(0, n - 1):
			left = 0
			right = 0
			for (letter, indexes) in list(dic.items()):
				if i >= indexes[0]:
					left += 1
				if i + 1 <= indexes[1]:
					right += 1
			if left == right:
				output += 1
		return output


from collections import Counter

class Solution:

	def numSplits(self, s: str) -> int:
		prev_counter = {}
		post_counter = dict(Counter(s))
		count = 0
		for partition in range(len(s)):
			(prev, post) = (s[:partition], s[partition:])
			if not prev or not post:
				continue
			curr = prev[-1]
			if curr not in prev_counter:
				prev_counter[curr] = 0
			prev_counter[curr] += 1
			post_counter[curr] -= 1
			if post_counter[curr] == 0:
				post_counter.pop(curr)
			if len(prev_counter) == len(post_counter):
				count += 1
		return count


class Solution:

	def sub(self, h, h2):
		nh = h.copy()
		for k in h2:
			if k in nh:
				nh[k] = nh[k] - h2[k]
				if nh[k] == 0:
					del nh[k]
		return nh

	def numSplits(self, s: str) -> int:
		h = {}
		for c in s:
			if c not in h:
				h[c] = 0
			h[c] = h[c] + 1
		ct = 0
		h2 = {}
		for (i, c) in enumerate(s):
			if c not in h2:
				h2[c] = 0
			h2[c] = h2[c] + 1
			uh = self.sub(h, h2)
			if len(h2) == len(uh):
				ct = ct + 1
		return ct


from collections import defaultdict, Counter

class Solution:

	def numSplits(self, s: str) -> int:
		len_s = len(s)
		if len_s == 0:
			return 0
		if len_s == 1:
			return 1
		nb_good_splits = 0
		left_counter = defaultdict(int)
		right_counter = Counter(s)
		for i in range(1, len_s):
			(left, right) = (s[0:i], s[i:])
			swing_letter = left[-1]
			left_counter[swing_letter] += 1
			right_counter[swing_letter] -= 1
			if right_counter[swing_letter] == 0:
				del right_counter[swing_letter]
			if len(left_counter) == len(right_counter):
				nb_good_splits += 1
		return nb_good_splits


class Solution:

	def numSplits(self, s: str) -> int:
		b_c = collections.defaultdict(lambda : 0)
		a_c = dict(collections.Counter(list(s)))
		ans = 0
		for (i, ch) in enumerate(list(s)):
			b_c[ch] += 1
			a_c[ch] -= 1
			if len({k for (k, v) in list(b_c.items()) if v > 0}) == len({k for (k, v) in list(a_c.items()) if v > 0}):
				ans += 1
		return ans


class Solution:

	def numSplits(self, s: str) -> int:
		good_splits = 0
		first_map = {}
		s_map = {}
		for letter in s:
			if s_map.get(letter):
				s_map[letter] += 1
			else:
				s_map[letter] = 1
		for split_point in range(len(s)):
			if first_map.get(s[split_point]):
				first_map[s[split_point]] = first_map[s[split_point]] + 1
			else:
				first_map[s[split_point]] = 1
			s_map[s[split_point]] = s_map[s[split_point]] - 1
			f_keys = [k for (k, v) in list(first_map.items()) if v > 0]
			s_keys = [k for (k, v) in list(s_map.items()) if v > 0]
			if len(f_keys) == len(s_keys):
				good_splits += 1
		return good_splits


class Solution:

	def numSplits(self, s: str) -> int:
		if len(s) <= 1:
			return 0
		left = len(s) * [0]
		right = len(s) * [0]
		seen = set(s[0])
		left[0] = 1
		for i in range(1, len(s)):
			if s[i] not in seen:
				seen.add(s[i])
				left[i] = left[i - 1] + 1
			else:
				left[i] = left[i - 1]
		seen = set()
		rtotal = 0
		count = 0
		for i in range(len(s) - 1, 0, -1):
			if s[i] not in seen:
				seen.add(s[i])
				rtotal += 1
			if rtotal == left[i - 1]:
				count += 1
			elif rtotal > left[i - 1]:
				break
		return count


class Solution:

	def numSplits(self, s: str) -> int:
		characters = []
		possibleSplits = 0
		for i in range(len(s)):
			if s[i] not in characters:
				characters.append(s[i])
		for i in range(len(s)):
			leftChars = 0
			rightChars = 0
			leftSide = s[:i]
			rightSide = s[i:]
			for j in range(len(characters)):
				if characters[j] in leftSide:
					leftChars += 1
				if characters[j] in rightSide:
					rightChars += 1
			if leftChars == rightChars:
				possibleSplits += 1
		return possibleSplits


from collections import Counter

class Solution:

	def numSplits(self, s: str) -> int:
		c = 0
		c1 = Counter()
		c2 = Counter(s)
		for i in range(len(s)):
			c1[s[i]] += 1
			c2[s[i]] -= 1
			if self.Count(c1) == self.Count(c2):
				c += 1
		return c

	def Count(self, counter):
		return sum([1 for k in counter if counter[k] != 0])


class Solution:

	def numSplits(self, s: str) -> int:
		s_len = len(s)
		if s_len == 0 or s_len == 1:
			return 0
		seen = set()
		dp = [0 for _ in range(s_len - 1)]
		dp[0] = 1
		seen.add(s[0])
		for i in range(1, s_len - 1):
			if s[i] in seen:
				dp[i] = dp[i - 1]
			else:
				seen.add(s[i])
				dp[i] = dp[i - 1] + 1
		seen = set()
		acc = 0
		count = 0
		for i in range(s_len - 1, 0, -1):
			if s[i] not in seen:
				seen.add(s[i])
				acc += 1
			if acc == dp[i - 1]:
				count += 1
		return count


class Solution:

	def numSplits(self, s: str) -> int:
		cnt = 0
		l_set = set()
		d = {c: s.count(c) for c in set(s)}
		for c in s:
			l_set.add(c)
			d[c] -= 1
			if d[c] == 0:
				d.pop(c, None)
			if len(l_set) == len(d):
				cnt += 1
		return cnt


class Solution:

	def numSplits(self, s: str) -> int:
		dictionary = {}
		sol = 0
		for i in range(len(s)):
			dictionary[s[i]] = i
		dictionary2 = {}
		for i in range(len(s) - 1):
			dictionary2[s[i]] = i
			if i == dictionary[s[i]]:
				dictionary.pop(s[i])
			if len(dictionary) == len(dictionary2):
				sol += 1
		return sol


class Solution:

	def numSplits(self, s: str) -> int:
		uniqueLeft = 0
		uniqueRight = 0
		ans = 0
		leftDict = {}
		rightDict = {}
		for i in s:
			if i in rightDict:
				rightDict[i] += 1
			else:
				rightDict[i] = 1
				uniqueRight += 1
		for i in s:
			if i in leftDict:
				leftDict[i] += 1
			else:
				leftDict[i] = 1
				uniqueLeft += 1
			rightDict[i] -= 1
			if rightDict[i] == 0:
				uniqueRight -= 1
			if uniqueRight == uniqueLeft:
				ans += 1
		return ans


class Solution:

	def numSplits(self, s: str) -> int:
		N = len(s)
		left = [0] * (N + 1)
		seen = set()
		for i in range(1, N + 1):
			c = s[i - 1]
			if c not in seen:
				left[i] = left[i - 1] + 1
				seen.add(c)
			else:
				left[i] = left[i - 1]
		right = [0] * (N + 1)
		seen.clear()
		for i in range(N - 1, -1, -1):
			c = s[i]
			if c not in seen:
				right[i] = right[i + 1] + 1
				seen.add(c)
			else:
				right[i] = right[i + 1]
		good = 0
		for i in range(N + 1):
			if left[i] == right[i]:
				good += 1
		return good


class Solution:

	def numSplits(self, s: str) -> int:
		set_f = set()
		map_b = defaultdict(int)
		for c in s:
			map_b[c] += 1
		num = 0
		for c in s:
			map_b[c] -= 1
			if not map_b[c]:
				del map_b[c]
			set_f.add(c)
			if len(set_f) == len(map_b):
				num += 1
		return num


from collections import defaultdict

class Solution:

	def numSplits(self, s: str) -> int:
		rst = 0
		lDict = defaultdict(int)
		rDict = defaultdict(int)
		lDict[s[0]] = 1
		for char in s[1:]:
			rDict[char] += 1
		if len(rDict) == len(lDict):
			rst += 1
		for char in s[1:-1]:
			rDict[char] -= 1
			if rDict[char] == 0:
				rDict.pop(char)
			lDict[char] += 1
			if len(rDict) == len(lDict):
				rst += 1
		return rst


import collections

class Solution:

	def numSplits(self, s: str) -> int:
		leftMap = collections.defaultdict(int)
		rightMap = collections.defaultdict(int)
		for ch in s:
			rightMap[ch] += 1
		output = 0
		for ch in s:
			rightMap[ch] -= 1
			if rightMap[ch] == 0:
				del rightMap[ch]
			leftMap[ch] += 1
			if len(rightMap) == len(leftMap):
				output += 1
		return output


class Solution:

	def numSplits(self, s: str) -> int:
		initial = {}
		for char in s:
			if char in initial:
				initial[char] += 1
			else:
				initial[char] = 1
		other = {}
		output = 0
		for char in s:
			initial[char] -= 1
			if initial[char] == 0:
				del initial[char]
			other[char] = 1
			if len(initial) == len(other):
				output += 1
		return output


from collections import defaultdict

class Solution:

	def numSplits(self, s: str) -> int:
		hmap = defaultdict(int)
		for ele in s:
			hmap[ele] += 1
		count = 0
		size = len(hmap)
		second_map = defaultdict(int)
		for i in range(len(s)):
			c = s[i]
			second_map[c] += 1
			hmap[c] -= 1
			if hmap[c] == 0:
				del hmap[c]
			if len(second_map) == len(hmap):
				count += 1
			elif len(second_map) > len(hmap):
				break
		return count


class Solution:

	def numSplits(self, s: str) -> int:
		n = len(s)
		lc = [1] * n
		rc = [1] * n
		ls = set()
		rs = set()
		for i in range(n):
			ls.add(s[i])
			rs.add(s[-(i + 1)])
			lc[i] = len(ls)
			rc[-(i + 1)] = len(rs)
		r = 0
		for i in range(n - 1):
			if lc[i] == rc[i + 1]:
				r += 1
		return r


class Solution:

	def numSplits(self, s: str) -> int:
		(lc, rc) = ([], [])
		(ls, rs) = (set(), set())
		for c in s:
			ls.add(c)
			lc.append(len(ls))
		for c in reversed(s):
			rs.add(c)
			rc.append(len(rs))
		res = 0
		rc = rc[::-1]
		for i in range(len(lc) - 1):
			if lc[i] == rc[i + 1]:
				res += 1
		return res


class Solution:

	def numSplits(self, s: str) -> int:
		auxDict = {}
		auxLeftToRight = [0] * len(s)
		count = 0
		for pos in range(len(s)):
			if s[pos] not in auxDict:
				auxDict[s[pos]] = 1
				count += 1
			auxLeftToRight[pos] = count
		auxDict = {}
		auxRightToLeft = [0] * len(s)
		count = 0
		for pos in range(len(s) - 1):
			if s[len(s) - 1 - pos] not in auxDict:
				auxDict[s[len(s) - 1 - pos]] = 1
				count += 1
			auxRightToLeft[len(s) - 2 - pos] = count
		total = 0
		for pos in range(len(s)):
			if auxLeftToRight[pos] == auxRightToLeft[pos]:
				total += 1
		return total


from collections import Counter

class Solution:

	def numSplits(self, s: str) -> int:
		n = len(s)
		prefix = [0] * n
		suffix = [0] * n
		pset = set()
		sset = set()
		ans = 0
		for i in range(0, n):
			l = s[i]
			r = s[n - i - 1]
			pset.add(l)
			sset.add(r)
			prefix[i] = len(pset)
			suffix[n - 1 - i] = len(sset)
		for i in range(0, n - 1):
			if prefix[i] == suffix[i + 1]:
				ans = ans + 1
		return ans


class Solution:

	def numSplits(self, s: str) -> int:
		seen_letters = []
		preprocess_prefix = [0]
		for i in range(len(s)):
			if s[i] not in seen_letters:
				seen_letters.append(s[i])
			preprocess_prefix.append(len(seen_letters))
		seen_letters = []
		preprocess_postfix = [0]
		for i in range(len(s) - 1, -1, -1):
			if s[i] not in seen_letters:
				seen_letters.append(s[i])
			preprocess_postfix.append(len(seen_letters))
		preprocess_postfix.reverse()
		count = 0
		for i in range(len(preprocess_postfix)):
			if preprocess_postfix[i] == preprocess_prefix[i]:
				count += 1
		return count


class Solution:

	def numSplits(self, s: str) -> int:
		count = 0
		(left, right) = (defaultdict(int), Counter(s))
		count = 0
		for letter in s:
			left[letter] += 1
			right[letter] -= 1
			if right[letter] == 0:
				del right[letter]
			count += len(left) == len(right)
		return count


class Solution:

	def numSplits(self, s: str) -> int:
		(le_set, ri_set) = ([s[0]], [s[-1]])
		(le_arr, ri_arr) = ([1] * len(s), [1] * len(s))
		for i in range(1, len(s)):
			le_arr[i] = le_arr[i - 1]
			if s[i] not in le_set:
				le_set.append(s[i])
				le_arr[i] += 1
		for i in range(len(s) - 2, -1, -1):
			ri_arr[i] = ri_arr[i + 1]
			if s[i] not in ri_set:
				ri_set.append(s[i])
				ri_arr[i] += 1
		cnt = 0
		for i in range(0, len(s) - 1):
			if le_arr[i] == ri_arr[i + 1]:
				cnt += 1
		return cnt


class Solution:

	def numSplits(self, s: str) -> int:
		total_chars_1 = defaultdict(int)
		total_chars_1[s[0]] = 1
		total_chars_2 = defaultdict(int)
		splits = 0
		for i in range(1, len(s)):
			total_chars_2[s[i]] += 1
		for i in range(len(s) - 1):
			if len(total_chars_1) == len(total_chars_2):
				splits += 1
			total_chars_1[s[i + 1]] += 1
			total_chars_2[s[i + 1]] -= 1
			if total_chars_2[s[i + 1]] == 0:
				del total_chars_2[s[i + 1]]
		return splits


class Solution:

	def numSplits(self, s: str) -> int:
		c = Counter(s)
		res = 0
		d = dict()
		for (i, v) in enumerate(s):
			if v not in d:
				d[v] = 1
			else:
				d[v] += 1
			c[v] -= 1
			if c[v] == 0:
				del c[v]
			if len(c) == len(d):
				res += 1
		return res


class Solution:

	def numSplits(self, s: str) -> int:
		counter = 0
		left = defaultdict(int)
		right = defaultdict(int)
		for c in s:
			right[c] += 1
		for i in range(len(s)):
			left[s[i]] += 1
			right[s[i]] -= 1
			if right[s[i]] == 0:
				right.pop(s[i])
			if len(left.keys()) == len(right.keys()):
				counter += 1
		return counter


class Solution:

	def numSplits(self, s: str) -> int:
		left_count = collections.Counter()
		right_count = collections.Counter(s)
		ans = 0
		for ch in s:
			left_count[ch] += 1
			right_count[ch] -= 1
			if right_count[ch] == 0:
				del right_count[ch]
			if len(left_count) == len(right_count):
				ans += 1
		return ans


class Solution:

	def numSplits(self, s: str) -> int:
		leftCount = collections.Counter()
		rightCount = collections.Counter(s)
		res = 0
		for c in s:
			leftCount[c] += 1
			rightCount[c] -= 1
			if rightCount[c] == 0:
				del rightCount[c]
			if len(rightCount) == len(leftCount):
				res += 1
		return res


class Solution:

	def numSplits(self, s: str) -> int:
		left = sorted([s.find(l) for l in set(s)]) + [len(s)]
		right = sorted([s.rfind(l) for l in set(s)], reverse=True) + [0]
		ind = max((ind for ind in range(len(left)) if left[ind] <= right[ind]))
		return min(right[ind], left[ind + 1]) - max(left[ind], right[ind + 1])


class Solution:

	def numSplits(self, s: str) -> int:
		s_cnt = Counter(s)
		p_cnt = defaultdict(int)
		count = 0
		for ch in s:
			p_cnt[ch] += 1
			s_cnt[ch] -= 1
			if s_cnt[ch] == 0:
				del s_cnt[ch]
			if len(s_cnt.keys()) == len(p_cnt.keys()):
				count += 1
		return count


from collections import Counter

class Solution:

	def numSplits(self, s: str) -> int:
		l_dict = Counter()
		r_dict = Counter(s)
		counter = 0
		print(r_dict)
		for i in s:
			r_dict[i] -= 1
			l_dict[i] = l_dict.get(i, 0) + 1
			if r_dict[i] == 0:
				del r_dict[i]
			if len(l_dict) == len(r_dict):
				counter += 1
		return counter


class Solution:

	def numSplitsBF(self, s: str) -> int:
		cntr = 0
		for i in range(1, len(s)):
			(a, b) = (collections.Counter(s[:i]), collections.Counter(s[i:]))
			if len(a) == len(b):
				cntr += 1
		return cntr

	def numSplits(self, s: str) -> int:
		a = collections.defaultdict(int)
		a[s[0]] = 1
		b = collections.Counter(s[1:])
		pntr = 1
		cntr = 0 if len(a) != len(b) else 1
		while pntr < len(s):
			a[s[pntr]] += 1
			b[s[pntr]] -= 1
			if b[s[pntr]] == 0:
				del b[s[pntr]]
			if len(a) == len(b):
				cntr += 1
			pntr += 1
		return cntr


class Solution:

	def numSplits(self, s: str) -> int:
		left = {s[0]: 1}
		right = {}
		for i in range(1, len(s)):
			right[s[i]] = right.get(s[i], 0) + 1
		middle_i = 1
		count = 0
		while middle_i < len(s):
			if len(left) == len(right):
				count += 1
			middle = s[middle_i]
			right[middle] -= 1
			if right[middle] == 0:
				right.pop(middle)
			left[middle] = left.get(middle, 0) + 1
			middle_i += 1
		return count


from collections import Counter

class Solution:

	def numSplits(self, s: str) -> int:
		left_counts = {s[0]: 1}
		right_counts = Counter(s[1:])
		split_count = 0
		if len(list(left_counts.items())) == len(list(right_counts.items())):
			split_count += 1
		for i in range(1, len(s)):
			if s[i] in left_counts:
				left_counts[s[i]] += 1
			else:
				left_counts[s[i]] = 1
			if right_counts[s[i]] == 1:
				del right_counts[s[i]]
			else:
				right_counts[s[i]] -= 1
			if len(list(left_counts.items())) == len(list(right_counts.items())):
				split_count += 1
		return split_count


class Solution:

	def numSplits(self, ss: str) -> int:
		a = set()
		k = {}
		p = {}
		n = len(ss)

		def myfunc(s, aa):
			for i in range(n - 1):
				if s[i] not in a:
					a.add(s[i])
					aa[i] = 1
				else:
					aa[i] = 0
				if i != 0:
					aa[i] += aa[i - 1]
		myfunc(ss, k)
		a.clear()
		myfunc(ss[::-1], p)
		ans = 0
		for j in range(n - 1):
			if k[j] == p[n - 1 - (j + 1)]:
				ans += 1
		return ans


class Solution:

	def numSplits(self, s: str) -> int:
		leftMap = {}
		rightMap = {}
		for j in range(len(s)):
			rightMap[s[j]] = rightMap.get(s[j], 0) + 1
		i = 0
		result = 0
		while i < len(s) - 1:
			leftMap[s[i]] = leftMap.get(s[i], 0) + 1
			rightMap[s[i]] = rightMap[s[i]] - 1
			if rightMap.get(s[i], 0) <= 0:
				rightMap.pop(s[i])
			if len(leftMap) == len(rightMap):
				result += 1
			i += 1
		return result


class Solution:

	def numSplits(self, s: str) -> int:
		left = Counter()
		right = Counter(s)
		res = 0
		for ch in s:
			if right[ch] == 1:
				del right[ch]
			else:
				right[ch] -= 1
			left[ch] += 1
			if len(list(left.keys())) == len(list(right.keys())):
				res += 1
		return res


from collections import Counter

class Solution:

	def numSplits(self, s: str) -> int:
		c2nl = Counter('')
		c2nr = Counter(s)
		n = len(s)
		ans = 0
		for i in range(n - 1):
			c2nl[s[i]] += 1
			c2nr[s[i]] -= 1
			if c2nr[s[i]] == 0:
				del c2nr[s[i]]
			if len(c2nl) == len(c2nr):
				ans += 1
		return ans


class Solution:

	def numSplits(self, s: str) -> int:
		p = int
		q = int
		ll = len(s)
		if ll < 2:
			return 0
		ns = len(set(s))
		np = nq = 0
		for ii in range(1, ll):
			if len(set(s[:ii])) == ns:
				np = ii
				break
		for ii in range(1, ll):
			if len(set(s[ll - ii:])) == ns:
				nq = ll - ii
				break
		if np <= nq:
			return nq - np + 1
		ans = 0
		for ii in range(1, ll):
			p = len(set(s[:ii]))
			q = len(set(s[ii:]))
			if p == q:
				ans += 1
			elif p > q:
				return ans
		return ans


from collections import Counter

class Solution:

	def numSplits(self, s: str) -> int:
		s1 = Counter()
		s2 = Counter(s)
		count = 0
		for a in s:
			s1[a] += 1
			s2[a] -= 1
			if s2[a] == 0:
				s2.pop(a)
			if len(s1) == len(s2):
				count += 1
		return count


class Solution:

	def numSplits(self, s: str) -> int:
		dic_b = {}
		for i in s[1:]:
			if i not in dic_b:
				dic_b[i] = 1
			else:
				dic_b[i] += 1
		b_count = len(dic_b)
		a = list(s[:1])
		a_count = 1
		count = int(b_count == a_count)
		ix = 1
		while ix < len(s):
			if s[ix] not in a:
				a_count += 1
			a.append(s[ix])
			dic_b[s[ix]] -= 1
			if dic_b[s[ix]] == 0:
				b_count -= 1
			count += int(a_count == b_count)
			ix += 1
		return count


from collections import Counter

def increment_counter(counter, key):
	counter[key] += 1

def decrement_counter(counter, key):
	counter[key] -= 1
	if counter[key] == 0:
		del counter[key]

def naive_solution(s: str) -> int:
	total = Counter(s)
	count = 0
	p = Counter()
	for char in s:
		p[char] += 1
		q = total - p
		if len(p) == len(q):
			count += 1
	return count

def optimized(s: str) -> int:
	prefix = Counter()
	suffix = Counter(s)
	count = 0
	for char in s:
		increment_counter(prefix, char)
		decrement_counter(suffix, char)
		if len(prefix) == len(suffix):
			count += 1
	return count

class Solution:

	def numSplits(self, s: str) -> int:
		return optimized(s)


from collections import Counter

class Solution:

	def numSplits(self, s: str) -> int:
		hist_left = Counter(s[:1])
		hist_right = Counter(s[1:])
		count = 0
		for i in range(1, len(s)):
			v = s[i]
			if len(list(hist_left.keys())) == len(list(hist_right.keys())):
				count += 1
			hist_left[v] += 1
			if hist_right[v] == 1:
				del hist_right[v]
			else:
				hist_right[v] -= 1
		return count


class Solution:

	def numSplits(self, s: str) -> int:
		right = collections.Counter(s)
		left = collections.defaultdict(int)
		res = 0
		for i in range(len(s) - 1):
			c = s[i]
			right[c] -= 1
			if not right[c]:
				del right[c]
			left[c] += 1
			if len(left) == len(right):
				res += 1
		return res


class Solution:

	def numSplits(self, s: str) -> int:
		left_unique = [0 for x in range(len(s))]
		right_unique = [0 for x in range(len(s))]
		left_set = set()
		right_set = set()
		for x in range(len(s)):
			if s[x] not in left_set:
				left_set.add(s[x])
				if x > 0:
					left_unique[x] = left_unique[x - 1] + 1
				else:
					left_unique[x] += 1
			else:
				left_unique[x] = left_unique[x - 1]
			if s[len(s) - 1 - x] not in right_set:
				right_set.add(s[len(s) - x - 1])
				if x > 0:
					right_unique[len(s) - x - 1] = right_unique[len(s) - x] + 1
				else:
					right_unique[len(s) - x - 1] += 1
			else:
				right_unique[len(s) - x - 1] = right_unique[len(s) - x]
		min_splits = 0
		for x in range(1, len(s)):
			if left_unique[x - 1] == right_unique[x]:
				min_splits += 1
		return min_splits


class Solution:

	def numSplits(self, s: str) -> int:
		fila = {}
		tot = len(set(s))
		x = set()
		for i in range(len(s)):
			x.add(s[i])
			if len(x) == tot:
				fa = i
				break
		x = set()
		for i in range(len(s) - 1, -1, -1):
			x.add(s[i])
			if len(x) == tot:
				la = i
				break
		if fa <= la:
			return la - fa
		for (i, c) in enumerate(s):
			if c not in fila:
				fila[c] = [i, i]
			else:
				fila[c][1] = i
		(firsts, lasts) = (set(), set())
		for (a, b) in fila.values():
			firsts.add(a)
			lasts.add(b)
		ret = 0
		(cl, cr) = (0, len(fila))
		for i in range(len(s) - 1):
			if i in firsts:
				cl += 1
			if i in lasts:
				cr -= 1
			ret += int(cl == cr)
			if cr < cl:
				break
		return ret


class Solution:

	def numSplits(self, s: str) -> int:
		if len(s) == 1:
			return 0
		ln = len(s)
		ans = 0
		t1 = {}
		t2 = {}
		(l1, l2) = (0, 0)
		t1[s[0]] = 1
		for i in range(1, ln):
			if s[i] in list(t2.keys()):
				t2[s[i]] += 1
			else:
				t2[s[i]] = 1
		if len(list(t1.keys())) == len(list(t2.keys())):
			ans += 1
		for i in range(1, ln):
			if s[i] in list(t1.keys()):
				t1[s[i]] += 1
			else:
				t1[s[i]] = 1
			t2[s[i]] -= 1
			if t2[s[i]] == 0:
				del t2[s[i]]
			if len(t1) == len(t2):
				ans += 1
		return ans


class Solution:

	def make_hist(self, array: str) -> dict:
		hist = {}
		for s in array:
			if s not in list(hist.keys()):
				hist[s] = 1
			else:
				hist[s] += 1
		return hist

	def numSplits(self, s: str) -> int:
		hist_left = self.make_hist(s[:1])
		hist_right = self.make_hist(s[1:])
		count = 0
		for i in range(1, len(s)):
			v = s[i]
			if len(list(hist_left.keys())) == len(list(hist_right.keys())):
				count += 1
			if v not in list(hist_left.keys()):
				hist_left[v] = 1
			else:
				hist_left[v] += 1
			if v in list(hist_right.keys()):
				if hist_right[v] == 1:
					del hist_right[v]
				else:
					hist_right[v] -= 1
		return count


class Solution:

	def numSplits(self, s: str) -> int:
		left_map = {}
		right_map = {}
		unique_right = 0
		unique_left = 0
		for i in range(len(s)):
			if s[i] not in right_map:
				right_map[s[i]] = 1
				unique_right += 1
			else:
				right_map[s[i]] += 1
		good_split = 0
		for i in range(len(s)):
			if s[i] not in left_map:
				left_map[s[i]] = 1
				unique_left += 1
			else:
				left_map[s[i]] += 1
			if right_map[s[i]] == 1:
				unique_right -= 1
			right_map[s[i]] -= 1
			if unique_left == unique_right:
				good_split += 1
		return good_split


from collections import Counter

class Solution:

	def numSplits(self, s: str) -> int:
		rightS = Counter(s)
		leftS = Counter()
		count = 0
		for c in s:
			leftS[c] += 1
			rightS[c] -= 1
			if rightS[c] == 0:
				del rightS[c]
			count += len(leftS.keys()) == len(rightS.keys())
		return count


class Solution:

	def numSplits(self, s: str) -> int:
		p_dict = {s[0]: 1}
		q_dict = {}
		for char in s[1:]:
			self.addToDict(q_dict, char)
		if len(p_dict.keys()) == len(q_dict.keys()):
			count = 1
		else:
			count = 0
		for i in range(1, len(s) - 1):
			char = s[i]
			self.removeFromDict(q_dict, char)
			self.addToDict(p_dict, char)
			if len(p_dict.keys()) == len(q_dict.keys()):
				count += 1
		return count

	def addToDict(self, my_dict, value):
		if my_dict.get(value) is None:
			my_dict[value] = 1
		else:
			my_dict[value] += 1

	def removeFromDict(self, my_dict, value):
		if my_dict.get(value) == 1:
			my_dict.pop(value)
		elif my_dict.get(value) > 1:
			my_dict[value] -= 1


class Solution:

	def numSplits(self, s: str) -> int:
		(cur, h) = (Counter(), Counter(s))
		cnt = 0
		for c in s:
			h[c] -= 1
			cur[c] += 1
			if h[c] == 0:
				del h[c]
			cnt += len(h) == len(cur)
		return cnt


class Solution:

	def numSplits(self, s: str) -> int:
		if not s or len(s) < 0:
			return 0
		right = {}
		left = {s[0]: 1}
		count = 0
		if len(left) == len(right):
			count += 1
		for i in range(1, len(s)):
			if s[i] in right:
				right[s[i]] += 1
			else:
				right[s[i]] = 1
		if len(left) == len(right):
			count += 1
		for i in range(1, len(s)):
			right[s[i]] -= 1
			if right[s[i]] == 0:
				del right[s[i]]
			if s[i] in left:
				left[s[i]] += 1
			else:
				left[s[i]] = 1
			if len(left) == len(right):
				count += 1
		return count


from collections import Counter

class Solution:

	def numSplits(self, s: str) -> int:
		(l, r) = ({}, Counter(s))
		ans = 0
		for i in range(len(s) - 1):
			if s[i] in l:
				l[s[i]] += 1
			else:
				l[s[i]] = 1
			if s[i] in r:
				r[s[i]] -= 1
				if r[s[i]] == 0:
					del r[s[i]]
			if len(l) == len(r):
				ans += 1
		return ans


class Solution:

	def numSplits(self, s: str) -> int:
		c = Counter(s)
		d = dict()
		r = 0
		for i in s:
			d[i] = 1
			if i in c:
				c[i] -= 1
			if c[i] == 0:
				del c[i]
			if len(c) == len(d):
				r += 1
		return r


class Solution:

	def numSplits(self, s: str) -> int:
		(p, q, ans) = (Counter(), Counter(s), 0)
		for c in s[:-1]:
			p[c] += 1
			q[c] -= 1
			if not q[c]:
				del q[c]
			ans += len(p) == len(q)
		return ans


class Solution:

	def numSplits(self, s: str) -> int:
		left_count = Counter()
		right_count = Counter(s)
		res = 0
		for c in s:
			left_count[c] += 1
			right_count[c] -= 1
			if right_count[c] == 0:
				del right_count[c]
			if len(left_count) == len(right_count):
				res += 1
		return res


class Solution:

	def numSplits(self, s: str) -> int:
		result1 = [[s[0]]]
		result2 = [[s[-1]]]
		n = len(s)
		for i in range(1, len(s)):
			list1 = list(result1[i - 1])
			list2 = list(result2[i - 1])
			if s[i] not in list1:
				list1.append(s[i])
			if s[n - 1 - i] not in list2:
				list2.append(s[n - 1 - i])
			result1.append(list1)
			result2.append(list2)
		result = 0
		result2.reverse()
		for i in range(len(s) - 1):
			if len(result1[i]) == len(result2[i + 1]):
				result += 1
		return result


class Solution:

	def numSplits(self, s: str) -> int:
		unique_chars = {}
		for (i, char) in enumerate(s):
			if char in unique_chars:
				(first, last) = unique_chars[char]
				unique_chars[char] = (first, i)
			else:
				unique_chars[char] = (i, i)
		n_unique_chars = len(list(unique_chars.keys()))
		events = []
		for (start, end) in list(unique_chars.values()):
			events.append((start, 1))
			events.append((end, -1))
		events.sort(key=lambda x: x[0])
		left_num = 0
		right_num = n_unique_chars
		total = 0
		start_good = None
		for (i, event_type) in events:
			if start_good is not None:
				return i - start_good
			if event_type == 1:
				left_num += 1
			else:
				right_num -= 1
			if left_num == right_num:
				start_good = i


from collections import Counter

class Solution:

	def numSplits(self, s):
		res = 0
		left = {}
		right = Counter(s)
		for i in range(len(s)):
			left[s[i]] = left.get(s[i], 0) + 1
			right[s[i]] -= 1
			if right[s[i]] == 0:
				del right[s[i]]
			if len(left) == len(right):
				res += 1
		return res


class Solution:

	def numSplits(self, s: str) -> int:
		if len(s) == 1:
			return 0
		lmap = collections.Counter(s[0:1])
		rmap = collections.Counter(s[1:])
		ans = 0
		for i in range(1, len(s)):
			if len(lmap) == len(rmap):
				ans += 1
			lmap.update([s[i]])
			rmap[s[i]] -= 1
			if not rmap[s[i]]:
				del rmap[s[i]]
		return ans


class Solution:

	def numSplits(self, s: str) -> int:
		res = 0
		fs = set()
		d = {}
		for x in s:
			if x not in d:
				d[x] = 1
			else:
				d[x] += 1
		i = 0
		while i < len(s):
			fs.add(s[i])
			if d[s[i]] > 1:
				d[s[i]] -= 1
			else:
				del d[s[i]]
			if len(fs) == len(set(d.keys())):
				res += 1
			i += 1
		return res


class Solution:

	def numSplits(self, string: str) -> int:

		def isValid(string, i):
			return 0 <= i < len(string)

		def getLength(string, unique, i):
			if isValid(string, i):
				unique.add(string[i])
				return len(unique)
			return len(unique)
		(left, right) = ([0] * len(string), [0] * len(string))
		(left_unique, right_unique) = (set(), set())
		reversed_string = string[::-1]
		for i in range(len(left)):
			left[i] = getLength(string, left_unique, i)
			right[len(right) - 1 - i] = getLength(reversed_string, right_unique, i)
		good_splits = 0
		for i in range(len(left) - 1):
			if right[i + 1] == left[i]:
				good_splits += 1
		return good_splits


class Solution:

	def numSplits(self, s: str) -> int:
		if len(s) == 0:
			return 0
		count = 0
		counterLeft = collections.Counter()
		counterRight = collections.Counter(s)
		for element in s:
			counterLeft[element] += 1
			counterRight[element] -= 1
			if counterRight[element] == 0:
				counterRight.pop(element)
			if len(counterLeft) == len(counterRight):
				count += 1
		return count


class Solution:

	def numSplits(self, s: str) -> int:
		if not s:
			return 0
		l_unique = set([])
		r_unique = set(s)
		good_splits = 0
		for (i, x) in enumerate(s):
			l_unique.add(x)
			if x not in s[i + 1:]:
				r_unique.discard(x)
			if len(l_unique) == len(r_unique):
				good_splits += 1
		return good_splits