Find the Number of “Balance” in the String

https://www.lintcode.com/problem/find-the-number-of-balance-in-the-string/solution

这道题如果暴力求解，用两遍set的length来求解会TLE

方法和Product Except Self 一模一样，维护左右两个array记录两边从0到n-1每个index的distinct char数量。用一个boolean array来记录该char是否被使用过之前，比用set来记录space complexity提高很多。

class Solution:
    """
    @param S: the string
    @return: return the number of “Balance” in the string
    """
    def find(self, S):
        # write your code here
        cnt = 0
        n = len(S)
        left = [0] * n
        right = [0] * n
        used = [False] * 26
        used2 = [False] * 26
        left[0] = 1
        curr = ord(S[0]) - ord("a")
        used[curr] = True
        for i in range(1,n):
            ch = ord(S[i]) - ord("a")
            if not used[ch]:
                left[i] = left[i-1]+1
                used[ch] = True
            else:
                left[i] = left[i-1]
        
        right[n-1] = 1 
        curr = ord(S[-1]) - ord("a")
        used2[curr] = True 
        for j in range(n-2,-1,-1):
            ch = ord(S[j]) - ord("a")
            if not used2[ch]:
                right[j] = right[j+1]+1
                used2[ch] = True
            else:
                right[j] = right[j+1]
        
        for i in range(n-1):
            if left[i] == right[i+1]:
                cnt+=1
        return cnt