深入解析力扣159题:至多包含两个不同字符的最长子串(滑动窗口法详细图解)

本文涉及的产品
云解析DNS,个人版 1个月
公共DNS(含HTTPDNS解析),每月1000万次HTTP解析
全局流量管理 GTM,标准版 1个月
简介: 深入解析力扣159题:至多包含两个不同字符的最长子串(滑动窗口法详细图解)

❤️❤️❤️ 欢迎来到我的博客。希望您能在这里找到既有价值又有趣的内容,和我一起探索、学习和成长。欢迎评论区畅所欲言、享受知识的乐趣!

期待与您一起探索技术、持续学习、一步步打怪升级 欢迎订阅本专栏❤️❤️

在本篇文章中,我们将详细解读力扣第159题“至多包含两个不同字符的最长子串”。通过学习本篇文章,读者将掌握如何使用滑动窗口的方法来解决这一问题,并了解相关的复杂度分析。每种方法都将配以详细的解释和ASCII图解,以便于理解。

问题描述

力扣第159题“至多包含两个不同字符的最长子串”描述如下:

给定一个字符串 s,找出至多包含两个不同字符的最长子串,并返回该子串的长度。

示例 1:

输入: s = "eceba"
输出: 3
解释: t 是 "ece",长度为 3。

示例 2:

输入: s = "ccaabbb"
输出: 5
解释: t 是 "aabbb",长度为 5。

解题思路

  1. 初步分析
  • 需要找到一个字符串 s 中最长的子串,该子串至多包含两个不同的字符。
  • 可以使用滑动窗口的方法来解决这个问题。
  1. 滑动窗口方法
  • 使用两个指针来表示窗口的左右边界,维护一个哈希表来存储窗口内字符的频率。
  • 当窗口内的不同字符数超过两个时,移动左指针缩小窗口,直到窗口内的不同字符数不超过两个。
  • 记录并更新窗口的最大长度。

方法:滑动窗口

  1. 步骤
  • 初始化两个指针 leftright,表示窗口的左右边界。
  • 初始化一个哈希表 char_count,用来存储窗口内字符的频率。
  • 使用一个变量 max_length 来记录最长子串的长度。
  • 使用一个循环来扩展窗口:
  • 将右指针指向的字符添加到哈希表中,并更新其频率。
  • 如果窗口内的不同字符数超过两个,移动左指针缩小窗口,直到窗口内的不同字符数不超过两个。
  • 更新最长子串的长度。
代码实现
def lengthOfLongestSubstringTwoDistinct(s):
    left, right = 0, 0
    char_count = {}
    max_length = 0
    while right < len(s):
        if s[right] in char_count:
            char_count[s[right]] += 1
        else:
            char_count[s[right]] = 1
        while len(char_count) > 2:
            char_count[s[left]] -= 1
            if char_count[s[left]] == 0:
                del char_count[s[left]]
            left += 1
        max_length = max(max_length, right - left + 1)
        right += 1
    return max_length
ASCII图解

假设输入字符串为 “eceba”,图解如下:

初始状态: s = "eceba", left = 0, right = 0, char_count = {}, max_length = 0
扩展窗口:
right = 0, char = 'e', char_count = {'e': 1}
right = 1, char = 'c', char_count = {'e': 1, 'c': 1}
max_length = 2
right = 2, char = 'e', char_count = {'e': 2, 'c': 1}
max_length = 3
收缩窗口:
right = 3, char = 'b', char_count = {'e': 2, 'c': 1, 'b': 1}
left = 1, char = 'e', char_count = {'e': 1, 'c': 1, 'b': 1}
left = 2, char = 'c', char_count = {'e': 1, 'b': 1}
max_length = 3
right = 4, char = 'a', char_count = {'e': 1, 'b': 1, 'a': 1}
left = 3, char = 'e', char_count = {'b': 1, 'a': 1}
max_length = 3
最终结果: max_length = 3

复杂度分析

  • 时间复杂度:O(n),其中 n 是字符串的长度。每个字符在滑动窗口内只会被处理一次。
  • 空间复杂度:O(1),使用了常数空间来存储字符的频率。

测试案例分析

  1. 测试案例 1
  • 输入: s = "eceba"
  • 输出: 3
  • 解释: 最长子串为 “ece”,长度为3。
  1. 测试案例 2
  • 输入: s = "ccaabbb"
  • 输出: 5
  • 解释: 最长子串为 “aabbb”,长度为5。

总结

本文详细解读了力扣第159题“至多包含两个不同字符的最长子串”,通过使用滑动窗口的方法,高效地解决了这一问题。希望读者通过本文的学习,能够在力扣刷题的过程中更加得心应手。

参考资料

  • 《算法导论》—— Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein
  • 力扣官方题解

🌹🌹如果觉得这篇文对你有帮助的话,记得一键三连关注、赞👍🏻、收藏是对作者最大的鼓励,非常感谢 ❥(^_-)

❤️❤️关注公众号 数据分析螺丝钉 回复 学习资料 领取高价值免费学习资料❥(^_-)

欢迎关注微信公众号 数据分析螺丝钉

相关文章
|
21天前
|
算法 搜索推荐
力扣每日一题 6/15 滑动窗口
力扣每日一题 6/15 滑动窗口
11 1
|
6天前
|
存储 SQL Python
`urllib.parse`模块是Python标准库`urllib`中的一个子模块,它提供了处理URL(统一资源定位符)的实用功能。这些功能包括解析URL、组合URL、转义URL中的特殊字符等。
`urllib.parse`模块是Python标准库`urllib`中的一个子模块,它提供了处理URL(统一资源定位符)的实用功能。这些功能包括解析URL、组合URL、转义URL中的特殊字符等。
|
9天前
|
存储 算法
经典的滑动窗口的题目 力扣 2799. 统计完全子数组的数目(面试题)
经典的滑动窗口的题目 力扣 2799. 统计完全子数组的数目(面试题)
|
1月前
|
算法
【LeetCode刷题】滑动窗口解决问题:串联所有单词的子串(困难)、最小覆盖子串(困难)
【LeetCode刷题】滑动窗口解决问题:串联所有单词的子串(困难)、最小覆盖子串(困难)
|
1月前
|
算法 容器
【LeetCode刷题】滑动窗口解决问题:水果成篮、找到字符串中所有字母异位词
【LeetCode刷题】滑动窗口解决问题:水果成篮、找到字符串中所有字母异位词
|
17天前
|
索引
821.字符的最短距离-力扣(LeetCode)
821.字符的最短距离-力扣(LeetCode)
9 0
|
21天前
|
算法 索引
力扣随机一题 位运算/滑动窗口/数组
力扣随机一题 位运算/滑动窗口/数组
15 0
|
21天前
|
算法
力扣经典150题解析之三十四:有效的数独
力扣经典150题解析之三十四:有效的数独
11 0
|
21天前
|
存储 算法 程序员
力扣经典150题第三十一题:无重复字符的最长子串
力扣经典150题第三十一题:无重复字符的最长子串
12 0
|
21天前
|
算法 搜索推荐 测试技术
力扣经典150题解析之二十九:三数之和
力扣经典150题解析之二十九:三数之和
12 0

推荐镜像

更多