最长01相等子串

给一个只由0和1组成的字符串，找一个最长的子串，要求这个子串里面0和1的数目相等。

解题思路：

这样一种巧妙的解法：定义一个数据 B[N]， B[i] 表示 A[0...i] 中 num_of_0 - num_of_1，即 0 的个数与1 的个数的差。 那么如果 arr[i] ~ arr[j] 是符合条件的子串，一定有 B[i] = B[j]，因为中间的部分 0、1 个数相等，相减等于0。 只需要扫一遍 A[N] 就能把 B[N] 构造出来了。

时间复杂度：O(n)，空间复杂度：O(n)

Python 实现：

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 出现的差值
            if B[i] == 0:  # 从字符串开始，0、1出现的次数相等
                lengest = i + 1
                continue
            # 字典中有，说明字典保存的下标到当前下标这一段，出现0与1的个数相等
            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'