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

Difficulty: interview

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)):
            # if s[i] in set_one:
            #     continue
            # else:
            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)):
            # if s_r[i] in set_two:
            #     continue
            # else:
            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
            
            # print(s[:point], s[point:], count1, count2)
            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
#         for i in range(1, n):
#             if len(set(s[:i])) == len(set(s[i:n])):
#                 output += 1
#             if len(set(s[:i])) > len(set(s[i:n])):
#                 break
#         return output
    
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
        # print(dic)
        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
            


from collections import Counter

class Solution:
    def numSplits(self, s: str) -> int:
        prev_counter = {}
        post_counter = 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)))
        
        # print('initial', b_c, a_c)
        
        ans = 0
        for i, ch in enumerate(list(s)):
            # print(i, ch)
            b_c[ch] += 1
            a_c[ch] -= 1
            # print(b_c, a_c)
            
            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])
        # right[-1] = 1
        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
                
        # count = 0
        # # print(left)
        # # print(right)
        # for i in range(0, len(s)-1):
        #     if left[i]== right[i+1]:
        #         count +=1
        #     elif right[i+1] < left[i]:
        #         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 numSplits111(self, s: str) -> int:
        s_len = len(s)
        if s_len == 0 or s_len == 1:
            return  0
        seen = set()
        dp = [0 for i 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

    def numSplits(self, s: str) -> int:
        
        n = len(s)
        
        if n <= 1:
            return 0
        
        #forward pass
        seen = set()
        dp = [0 for _ in range(n-1)]
        dp[0] = 1
        seen.add(s[0])
        
        for i in range(1,n-1):
            if s[i] in seen:
                dp[i] = dp[i-1]
            else:
                seen.add(s[i])
                dp[i] = dp[i-1] + 1
                
        count = 0
        
        #backward pass
        seen = set()
        current = 0
        for i in range(n-1, 0, -1):
            if s[i] not in seen:
                seen.add(s[i])
                current += 1
            
            if current == 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

# time complexity: O(26N), N = len(s)
#class Solution:
#    def numSplits(self, s: str) -> int:
#        N = len(s)
#        freq = [[0] * (N+1) for _ in range(26)] # cumulative freq of each character
#        for i in range(1, N+1):
#            for j in range(26):
#                if ord(s[i-1]) - ord('a') == j:
#                    freq[j][i] = freq[j][i-1] + 1
#                else:
#                    freq[j][i] = freq[j][i-1]
#
#        good = 0
#        for i in range(1, N):
#            left = 0
#            right = 0
#            for j in range(26):
#                if freq[j][i] > 0: # there is at least one chr(ord(j) + ord('a')) on the left of s[i]
#                    left += 1
#                if freq[j][i] < freq[j][-1]: # there is at least one chr(ord(j) + ord('a')) on the right of s[i]
#                    right += 1
#            if left == right:
#                good += 1
#        return good

# time complexity: O(3N), N = len(s)
class Solution:
    def numSplits(self, s: str) -> int:
        N = len(s)
        
        left = [0] * (N+1) # unique char in s[:left], exclude left
        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) # unique char in s[right:], include right
        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
            #print(lDict,rDict)
            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:
        # preprocess_prefix[k], number of different letters in s[:k]
        # preprocess_postfix[k], number of different letters in s[k:]
        
        # Fill preprocess_prefix
        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))
        
        # Fill preprocess_postfix[k]
        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)
        # print(le_arr[0])
        # print(ri_arr)
        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
        
        # print(le_arr)
        # print(ri_arr)
        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     # pre-populate\\
        
        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]) 
'''
\"aacaba\"
\"abcd\"
\"aaaaa\"
\"acbadbaada\"
\"a\"
\"abc\"
\"abcd\"
'''


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:
        #pseudo:
        #start left window at 0
        #have right window open for all letters in s
        #keep count for left and right
        #keep overall count
        #left woud start with first letter, right would be rest of letters
        #loop through each letter
        #left window should increase by one [i+1]
        #right window should decrease by 1
        #if the letter in the right dictionary already exists, then remove and decrease the right count             by 1
        #if current letter not in the left dictionary then +1 to left count and add to dictionary 
        #if left count and right counter are both equal to each other then add 1 to count 
        
        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 = s[:i], s[i:]
            # print(a, b)
            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]]
            # print(a, b)
            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
            
        #check if the left set has as many items as the right set
        #then we incremenet the middle pointer
        #remove the item from right
        #add it to left
        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) # k[i] gives,no of distinct letters,to left of left of index i+1 in ss
        a.clear()
        myfunc(ss[::-1],p)  # p[i] gives,no of distinct letters,to left of left of index i+1...in ss_reverse
        ans=0
        # print(k)
        # print(p)
        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
            
# method 2
#         prefix = [0] * len(s) # distinct number from s[0] to s[i]
#         suffix = [0] * len(s) # distinct number from s[len(s)-1] to s[i]
#         prefixMap = {}
#         suffixMap = {}
#         for i in range(len(s)):
#             j = len(s) - 1 - i
#             prefixMap[s[i]] = prefixMap.get(s[i], 0) + 1
#             suffixMap[s[j]] = suffixMap.get(s[j], 0) + 1
#             prefix[i] = len(prefixMap)
#             suffix[j] = len(suffixMap)
            
#         result = 0
#         k = 0
#         while (k < len(s)-1):
#             if (prefix[k] == suffix[k+1]):
#                 result += 1
#             k += 1
#         return result


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
            # print(\"leftMap\", leftMap)
            # print(\"rightMap\", rightMap)
                
        return result
            
# method 2
#         prefix = [0] * len(s) # distinct number from s[0] to s[i]
#         suffix = [0] * len(s) # distinct number from s[len(s)-1] to s[i]
#         prefixMap = {}
#         suffixMap = {}
#         for i in range(len(s)):
#             j = len(s) - 1 - i
#             prefixMap[s[i]] = prefixMap.get(s[i], 0) + 1
#             suffixMap[s[j]] = suffixMap.get(s[j], 0) + 1
#             prefix[i] = len(prefixMap)
#             suffix[j] = len(suffixMap)
            
#         result = 0
#         k = 0
#         while (k < len(s)-1):
#             if (prefix[k] == suffix[k+1]):
#                 result += 1
#             k += 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
            #print (right,left)
            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

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:
        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()  # initialize prefix as empty
    suffix = Counter(s)  # initialize suffix as total
    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 naive_solution(s)
        return optimized(s)
    


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

from collections import Counter

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

def decrement_counter(counter, key):
    if key in counter:
        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()  # initialize prefix as empty
    suffix = Counter(s)  # initialize suffix as total
    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 naive_solution(s)
        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)):
            # add to left map
            if s[i] not in left_map:
                left_map[s[i]] = 1
                unique_left += 1
            else:
                left_map[s[i]] += 1

            # remove from right map
            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:
        # set up splitting at idx 1
        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):
            # find the char here
            char = s[i]
            # remove from q, add to p
            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):
            # Add s[i] to l
            if s[i] in l:
                l[s[i]] += 1
            else:
                l[s[i]] = 1
            # Remove s[i] from r
            if s[i] in r:
                r[s[i]] -= 1
                if r[s[i]] == 0:
                    del r[s[i]]
            if len(l) == len(r):
                #print(i, l, 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])
            # print(list1, list2)
            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()
        # print(result1)
        # print(result2)
        for i in range(len(s)-1):
            if len(result1[i]) == len(result2[i+1]):
                result += 1
        return result

from collections import Counter
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:
        # stores 
        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
        #print(events)
        for i, event_type in events:
            #print(i, event_type, left_num, right_num)
            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
        
        # construct dict from 1 to last
        # iterate from 1 and remove the elm from dict (if 0 then del elm from dict) and add it to the set 
        # check if leng are equal
        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

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])
            # print(list1, list2)
            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()
        # print(result1)
        # print(result2)
        for i in range(len(s)-1):
            if len(result1[i]) == len(result2[n-1-(i+1)]):
                result += 1
        return result