最长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'

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏杂烩

使用javascript让项目支持热插拔 原

    突然想起之前做过的一个小项目,项目虽小,需求却不小,要求解析特定格式的字符串,并且特定格式并非一成不变,想要一套系统能够支持解析多变的规则且更改规则时不...

19320
来自专栏weixuqin 的专栏

数据结构学习笔记(串)

28590
来自专栏AILearning

一个面试题:截取字符串的函数,输入为一个字符串和字节数,输出为按字节截取的字符串

一个面试题: 编写一个截取字符串的函数,输入为一个字符串和字节数,输出为按字节截取的字符串。 但 是要保证汉字不被截半个,如“我ABC”4,应该截为“我AB”,...

25590
来自专栏java学习

面试题30(关于if的用法哪个是正确的?)

下列关于if的用法哪个是正确的? public class IfTest{ public static void main(string[]args){...

29050
来自专栏C/C++基础

C++实现字符串的分割和替换

代码主要说明: (1)tmp.find(target):查找子串第一次出现的下标; (2)string::npos:表示未查找到子串时返回的数值。MSD...

13520
来自专栏企鹅号快讯

Python之递归函数

Python之递归函数 好久没有更新内容了,也好久没有给大家打个招呼了,小白想死你们了。今天跟大家说说Python中的递归函数。 Python是支持递归函数的。...

26980
来自专栏极乐技术社区

使用ES6新特性开发微信小程序(4)

Symbol Type ES6引入了一种新的原始数据类型Symbol,表示独一无二的值。它是JavaScript语言的第七种数据类型,前六种是:Undefine...

27560
来自专栏Java帮帮-微信公众号-技术文章全总结

Java基础19(01)总结IO流,异常try…catch,throws,File类

1:异常(理解) (1)程序出现的不正常的情况。 (2)异常的体系 Throwable |--Error 严重问题,我们不处理。 |--Excepti...

43070
来自专栏cs

串匹配算法

问题:给定二个字符串S和T,在主串S中查找子串T的过程称之为字符串匹配问题(string matching,也称之为模式匹配)。在文本处理系统,操作系统,编译系...

366100
来自专栏JadePeng的技术博客

\x 开头编码的数据解码成中文

在python里,直接decode('utf-8')即可 >>> "\xE5\x85\x84\xE5\xBC\x9F\xE9\x9A\xBE\xE5\xBD\x...

1.6K120

扫码关注云+社区

领取腾讯云代金券