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
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 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
    

                
                
            
                
        
