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

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

• 推荐：数据分析螺丝钉的首页 格物致知 终身学习 期待您的关注
  

• 导航：

  • LeetCode解锁1000题: 打怪升级之旅：每题都包括3-5种算法，以及详细的代码实现，刷题面试跳槽必备
  • 漫画版算法详解：通过漫画的形式和动态GIF图片把复杂的算法每一步进行详细可视解读，看一遍就掌握
  • python源码解读：解读python的源代码与调用关系，快速提升代码质量
  • python数据分析可视化：企业实战案例：企业级数据分析案例与可视化，提升数据分析思维和可视化能力
  • 程序员必备的数学知识与应用：全面详细的介绍了工程师都必备的数学知识

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

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

问题描述

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

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

示例 1:

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

示例 2:

输入: s = "ccaabbb"
输出: 5
解释: t 是 "aabbb"，长度为 5。
1
2
3

解题思路

1. 初步分析：

   • 需要找到一个字符串 s 中最长的子串，该子串至多包含两个不同的字符。
   • 可以使用滑动窗口的方法来解决这个问题。

2. 滑动窗口方法：

   • 使用两个指针来表示窗口的左右边界，维护一个哈希表来存储窗口内字符的频率。
   • 当窗口内的不同字符数超过两个时，移动左指针缩小窗口，直到窗口内的不同字符数不超过两个。
   • 记录并更新窗口的最大长度。

方法：滑动窗口

1. 步骤：
   • 初始化两个指针 left 和 right，表示窗口的左右边界。
   • 初始化一个哈希表 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
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

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
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

复杂度分析

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

测试案例分析

1. 测试案例 1：

   • 输入: s = "eceba"
   • 输出: 3
   • 解释: 最长子串为 “ece”，长度为3。

2. 测试案例 2：

   • 输入: s = "ccaabbb"
   • 输出: 5
   • 解释: 最长子串为 “aabbb”，长度为5。

总结

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

参考资料

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

本文内容由网友自发贡献，转载请注明出处：【wpsshop博客】