最长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'本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2018.03.16 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录