题解 | #包含不超过两种字符的最长子串#

包含不超过两种字符的最长子串

https://www.nowcoder.com/practice/90d6a362fa7d4c519d557da797bb02ce

    LeetCode1839-所有元音按顺序排布的最长子字符串

# 1.首先如果数组长度小于5的话,不可能满足美丽的定义,将这种情况提前排除
# 2.遍历时分了几种情况判断:
# - 如果当前字符比上一个字符大于,当前子串长度+1, 种类+1
# -     当前字符比上一个字符等于,当前子串长度+1
# -     当前字符比上一个字符小,当前字串不美丽,重置长度和种类
# 3.如果当前子字符串没有以a开头的话,那么在进行下一个子字符串开始遍历之前,元音种类一定不会达到5,所以只要判断种类即可
# 4.当元音种类为5的时候,持续维护更新最终结果,取出最大值即可

class Solution:
    def longestBeautifulSubstring(self, word: str) -> int:
        # 输入不满长度5,返回0
        if len(word) < 5:
            return 0
        s_n = 1 # 当前种类
        s_l = 1 # 当前长度
        res = 0 # 记录最长的字符长度
        for i in range(1, len(word)):
            if word[i] > word[i-1]:
                s_l += 1
                s_n += 1
            elif word[i] == word[i-1]:
                s_l += 1
            elif word[i] < word[i-1]: # 重置长度和种类
                s_n = 1 # 种类
                s_l = 1 # 长度
            if s_n == 5:
                res = max(s_l, res)
        return res
 

LeetCode3-无重复字符的最长子串

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        res = 0 # 最长子词长度
        s_l = 0 # 当前子词长度
        hash = [] # 当前子词
        for i in range(len(s)):
            if s[i] not in hash: # 不重复字符
                hash.append(s[i]) # 当前子词扩充
                s_l += 1 # 当前子词长度+1
            else:
                res = max(res, s_l) # 遇到重复字符时,当前子词长度和res求最大值
                # 删除当前子词中包括重复字符之前的字符,并添加当前字符
                # eg:zabca, 把za删除,添加当前a,hash=bca
                while hash[0] != s[i]: # 
                    hash.pop(0)
                hash.pop(0)
                hash.append(s[i])
                # 当前子词长度更新
                s_l = len(hash)
        res = max(res, s_l)        
        return res

全部评论

相关推荐

不愿透露姓名的神秘牛友
昨天 17:51
点赞 评论 收藏
分享
门口唉提是地铁杀:之前b站被一个游戏demo深深的吸引了。看up主页发现是个初创公司,而且还在招人,也是一天60。二面的时候要我做一个登录验证和传输文件两个微服务,做完要我推到github仓库,还要我加上jaeger和一堆运维工具做性能测试并且面试的时候投屏演示。我傻乎乎的做完以后人家跟我说一句现在暂时不招人,1分钱没拿到全是白干
你的秋招第一场笔试是哪家
点赞 评论 收藏
分享
认真搞学习:这么良心的老板真少见
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务