給一個只由0和1組成的字符串，找一個最長的子串，要求這個子串里面0和1的數(shù)目相等。

解題思路：

這樣一種巧妙的解法：定義一個數(shù)據(jù) B[N]， B[i] 表示 A[0...i] 中 num_of_0 - num_of_1，即 0 的個數(shù)與1 的個數(shù)的差。 那么如果 arr[i] ~ arr[j] 是符合條件的子串，一定有 B[i] = B[j]，因為中間的部分 0、1 個數(shù)相等，相減等于0。 只需要掃一遍 A[N] 就能把 B[N] 構造出來了。

時間復雜度：O(n)，空間復雜度：O(n)

Python 實現(xiàn)：

class Solution:
    """
    @param s: 0、1子串
    @return: 最長 0、1相等子串的長度
    """
    def lengest01SubStr(self, s):
        count = [0, 0]
        B = [0] * len(s)
        dic = {}  # 保存0、1的差值
        lengest = 0
        for i in range(len(s)):
            count[int(s[i])] += 1
            B[i] = count[0] - count[1] # 0、1 出現(xiàn)的差值
            if B[i] == 0:  # 從字符串開始，0、1出現(xiàn)的次數(shù)相等
                lengest = i + 1
                continue
            # 字典中有，說明字典保存的下標到當前下標這一段，出現(xiàn)0與1的個數(shù)相等
            if B[i] in dic:
                lengest = max(lengest, i - dic[B[i]]) # 更新最長子串
            else:
                dic[B[i]] = i
        return lengest

a = '1011010'
b = '10110100'
print(Solution().lengest01SubStr(a)) # 6 # '011010'
print(Solution().lengest01SubStr(b)) # 8 # '10110100'