当前位置 : 主页 > 编程语言 > 其它开发 >

【LeetCode】159.至多包含两个不同字符的最长子串

来源:互联网 收集:自由互联 发布时间:2022-05-30
159.至多包含两个不同字符的最长子串 知识点:字符串;滑动窗口 题目描述 给定一个字符串 s ,找出 至多 包含两个不同字符的最长子串 t 。 注意: 对于 t 中重复字符,我们寻找的子
159.至多包含两个不同字符的最长子串

知识点:字符串;滑动窗口

题目描述

给定一个字符串 s ,找出 至多 包含两个不同字符的最长子串 t 。

注意:

对于 t 中重复字符,我们寻找的子字符串中该字符数量必须不少于 t 中该字符数量。
如果 s 中存在这样的子串,我们保证它是唯一的答案。

示例
示例 1:
输入: "eceba"
输出: 3
解释: t 是 "ece",长度为3。


示例 2:
输入: "ccaabbb"
输出: 5
解释: t 是 "aabbb",长度为5。


解法一:滑动窗口

这其实也是滑动窗口的一道典型题目
刚看题目,最长子串,其实应该自然的想到滑动窗口。 最大,往往都是right向右移动寻找最优解,然后破坏了条件,然后left移动,缩小窗口,继续形成可行解;
对应到这道题目:
1.right右移,试图寻找一个最长窗口,直至破坏了条件,也就是包含了第三个字符

步骤一我们需要在窗口内含有第三个字符的时候停下来,自然想到了哈希表,当哈希表长度为3的时候,证明第三个字符出现了,这时候就需要去移动左窗口了

2.left开始移动,缩小窗口

left移动到哪个位置呢?我们的目的是让left移动后窗口重新满足条件,也就是只有两个字符,所以需要把一个字符移出去,也就是移到索引最小的位置+1处
例如例1,需要移动到c后面,而不能移动到第2个e后面,所以哈希表的value值应该是字符c最后一次出现的索引,而我们要的就是找到这两个字符谁的索引小,所以可以直接对其value形成的list进行排序,取第一个即可。

在这个过程中不断的更新最大窗口值

class resolution:
    def getlongestsubstring(self, s):
        hashtable = {}
        max_len = left = 0
        for i, cur_str in enumerate(s):
            if len(hashtable) < 3:
                hashtable[cur_str] = i   
            if len(hashtable) == 3:  
                index = sorted(hashtable.values())[0]  # 在哈希表里的最小索引,left移动,将这个字符移出窗口
                left = index + 1
                hashtable.pop(s[index])  # 移出哈希表
            max_len = max(max_len, i-left+1)
        return max_len
【文章转自日本多IP服务器 http://www.558idc.com/japzq.html提供,感恩】
上一篇:PyQt5 基本语法(八):样式控制
下一篇:没有了
网友评论