首页 > 其他分享 >吃透LeetCode 159:至多包含两个不同字符的最长子串

吃透LeetCode 159:至多包含两个不同字符的最长子串

时间:2024-12-31 09:30:20浏览次数:9  
标签:子串 字符 right 吃透 159 哈希 窗口 LeetCode left

开篇:刷题党必看!

在算法学习的江湖里,LeetCode 可是众多程序员的 “练武场”,其重要性不言而喻。从初出茅庐的新手,到经验丰富的技术大拿,大家都热衷于在这个平台上切磋算法技艺,提升编程功力。这里汇聚了各种巧妙构思的算法题,堪称是检验我们编程能力的 “试金石”。而掌握经典题目的解题思路,就像是手握利刃,能助我们在编程的征途中披荆斩棘,无论是应对日常工作中的复杂需求,还是准备让人紧张的技术面试,都能更加从容不迫。今天,咱们就一起深入剖析 LeetCode 上一道相当有嚼头的题目 ——“至多包含两个不同字符的最长子串”,看看如何巧妙地解开它的奥秘。
一、题目剖析

题目是这么说的:给你一个字符串 s ,请你找出至多包含两个不同字符的最长子串,并返回该子串的长度。
什么意思呢?比如说给了字符串 “eceba”,咱们要在这个字符串里,找到一个子串,这个子串里最多就两个不同的字符,然后找出满足这个条件的最长的子串,它的长度就是咱们要的答案。像 “eceba” 里,符合要求的最长子串就是 “ece”,长度为 3 。再看 “ccaabbb”,这里面 “aabbb” 是最长的满足条件的子串,长度是 5 。
这题目看起来好像不难,不就是找找子串嘛,但真动手做,就会发现里面暗藏玄机,要是没找对方法,很容易就陷进各种复杂的情况里出不来,时间复杂度 “蹭蹭” 就上去了。不过别慌,接下来咱们就一起探索高效的解题妙招。
二、滑动窗口解法来袭

(一)滑动窗口基础
在算法的奇妙世界里,滑动窗口可是解决这类问题的一把 “利器”。简单来说,它就像是一个能在字符串上灵活滑动的 “窗框”,窗框的两边分别由两个指针 left 和 right 把控。开始的时候,这两个指针都指向字符串的开头,也就是 left = 0,right = 0,框住的就是字符串开头的第一个字符,这就是初始的窗口。随着算法的推进,right 指针会像一个勤劳的探索者,一步步地向右移动,不断扩大这个窗口,去探索后面的字符;而 left 指针呢,则像是一个谨慎的守护者,当窗口内的情况不符合要求时,它就会适时地向右移动,缩小窗口,确保窗口里的字符始终满足题目的条件。通过这两个指针的默契配合,我们就能高效地遍历整个字符串,找到我们想要的最长子串。
(二)算法步骤详解
初始化:首先,咱们把指针 left 和 right 都放在字符串 s 的开头,也就是 left = 0,right = 0,这就好比把滑动窗口的窗框放在了字符串的最左端,准备开始探索之旅。同时,创建一个哈希表,这个哈希表就像是窗口的 “记忆小助手”,用来记录窗口内每个字符出现的次数。为啥要用哈希表呢?因为它查找、插入和删除元素的操作平均时间复杂度都是 O(1),能让咱们的算法跑得飞快,这在处理大规模数据的时候可太重要了。
窗口扩张:接着,让 right 指针闪亮登场,它开始逐步向右移动,每移动一步,就把新遇到的字符纳入窗口的 “怀抱”。具体怎么做呢?就是把这个新字符加入哈希表,并且更新它在哈希表中的出现次数,表示它在窗口里又出现了一次。比如说,字符串是 “eceba”,当 right 指向第一个 e 时,哈希表中就记录 e 出现了 1 次;当 right 再向右移动指向 c 时,哈希表就更新为 e 出现 1 次,c 出现 1 次。在这个过程中,咱们还要时刻留意窗口内不同字符的数量是不是超过了 2 。怎么判断呢?看哈希表的大小就行啦,如果哈希表的大小大于 2 ,那就意味着窗口里已经有超过两个不同的字符了,这时候就得赶紧进行下一步 —— 窗口收缩。
窗口收缩:一旦发现窗口内的字符数超标了,left 指针就得赶紧行动起来,它开始向右移动,一步一步地缩小窗口,就像把窗框往左边拉一样。在移动的过程中,要同步更新哈希表哦,把 left 指针移出去的字符在哈希表中的出现次数减 1 。要是这个字符的出现次数减到了 0 ,为了节省空间,还得把它从哈希表中移除。这么一番操作下来,窗口里就又只剩下两个不同的字符了,继续保持满足题目要求的状态。比如说,对于 “eceba”,当 right 指向 b 时,哈希表中此时有 e、c、b 三个字符,大小为 3 ,超过了 2 ,那么 left 指针就要向右移动,先把最左边的 e 的出现次数减 1 ,此时哈希表变成 e 出现 0 次,c 出现 1 次,b 出现 1 次,因为 e 出现次数为 0 了,就把 e 从哈希表移除,窗口就变成了 “ceb”,又符合最多两个不同字符的要求啦。
结果更新:在 left 和 right 指针不断移动,窗口持续滑动的整个过程中,咱们得时刻保持警惕,比较当前窗口的长度和已经记录下来的最大长度。要是发现当前窗口长度更长,那就赶紧更新最大长度的值,把它记下来。这样一轮操作下来,当整个字符串都遍历完,最终记录下来的最大长度,就是咱们苦苦寻觅的 “至多包含两个不同字符的最长子串” 的长度啦。
三、代码示例与解读

(一)Java 代码实现
class Solution {
public int lengthOfLongestSubstringTwoDistinct(String s) {
int n = s.length();
if (n < 3) return n; // 字符串长度小于 3 ,直接返回原长度

    int left = 0;
    int right = 0;
    int maxLen = 2;
    java.util.HashMap<Character, Integer> map = new java.util.HashMap<>();

    while (right < n) {
        map.put(s.charAt(right), right);  // 将当前字符及其位置存入哈希表
        right++;

        if (map.size() > 2) {
            int minIndex = Integer.MAX_VALUE;
            for (int value : map.values()) {  // 找出哈希表中值最小的键值对
                minIndex = Math.min(minIndex, value);
            }
            map.remove(s.charAt(minIndex));  // 移除最左边出现的字符
            left = minIndex + 1;  // 更新左指针位置
        }

        maxLen = Math.max(maxLen, right - left);  // 更新最大长度
    }

    return maxLen;
}

}

首先,判断字符串 s 的长度,如果小于 3 ,那它本身就是满足条件的最长子串,直接返回其长度。这是一个很巧妙的边界条件判断,能帮咱们节省不必要的计算。
接着初始化 left、right 指针都指向开头,也就是 0 ,再初始化最大长度 maxLen 为 2 ,同时创建一个哈希表 map,用来记录字符出现的位置。
进入 while 循环,随着 right 指针向右移动,每遇到一个新字符,就把它和对应的位置存入哈希表 map。这里就像是在给窗口里的字符 “登记打卡”,记录它们出现的最新位置。
一旦发现哈希表 map 的大小超过了 2 ,说明窗口里字符种类超标了,这时候就得找出窗口里最左边出现的字符,把它从哈希表移除,同时更新 left 指针到这个字符的下一个位置,就相当于把这个多余的字符 “踢出” 窗口。
不管有没有进行窗口收缩操作,都要时刻比较当前窗口的长度(right - left)和已记录的最大长度 maxLen,要是当前窗口更长,就更新 maxLen。
最后,当整个字符串遍历完,maxLen 里存的就是咱们要找的最长子串的长度,直接返回它就行。
(二)Python 代码实现
def lengthOfLongestSubstringTwoDistinct(s):
if len(s) < 3:
return len(s)
left = 0
right = 0
max_len = 0
hashmap = {}

while right < len(s):
    tail = s[right]
    hashmap[tail] = hashmap.get(tail, 0) + 1  # 更新字符出现次数

    while len(hashmap) > 2:
        head = s[left]
        hashmap[head] -= 1
        if hashmap[head] == 0:
            del hashmap[head]
        left += 1

    if len(hashmap) <= 2:
        max_len = max(max_len, right - left + 1)

    right += 1

return max_len

同样,先判断字符串 s 的长度,小于 3 就直接返回原长度,这一步和 Java 代码思路一致,是个很实用的 “小捷径”。
初始化 left、right 指针为 0 ,最大长度 max_len 为 0 ,还有一个空的哈希表 hashmap,用来记录字符出现的频次。
随着 right 指针向右移动,每遇到一个新字符,就更新哈希表 hashmap 中它的出现次数。这里用了 get 方法,如果字符是第一次出现,就默认它的出现次数为 0 ,然后再加 1 ,是不是很简洁巧妙?
当发现哈希表 hashmap 的长度大于 2 时,就要开始收缩窗口啦。把 left 指针指向的字符的出现次数减 1 ,要是减到 0 ,就直接从哈希表中移除这个字符,然后 left 指针向右移动一位,确保窗口里只剩下两个不同的字符。
只要哈希表 hashmap 的长度小于等于 2 ,就比较当前窗口长度(right - left + 1)和已有的最大长度 max_len,取较大值更新 max_len。这里的 right - left + 1 是因为 Python 里切片是左闭右开区间,所以要加 1 才是真正的窗口长度哦,这可是个容易忽略的小细节。
最后,整个字符串遍历完,返回 max_len,大功告成!
(三)C++ 代码实现
class Solution {
public:
int lengthOfLongestSubstringTwoDistinct(string s) {
int len = s.size();
if (len < 3) return len;
int left = 0, right = 0, ch = 0, ans = 0;
unordered_map<char, int> window;

    while (right < len) {
        char ch1 = s[right];
        if (window[ch1] == 0) {
            ch++;
        }
        window[ch1]++;

        while (ch > 2) {
            char ch2 = s[left++];
            window[ch2]--;
            if (window[ch2] == 0) {
                ch--;
            }
        }

        ans = max(ans, right - left + 1);
        right++;
    }

    return ans;
}

};

还是老样子,先判断字符串 s 的长度,小于 3 就直接返回原长,这个 “小窍门” 在 C++ 里同样适用。
初始化 left、right 指针为 0 ,ch 用来记录窗口内不同字符的数量,初始化为 0 ,还有结果 ans 也初始化为 0 ,同时创建一个无序哈希表 window,用来存放字符及其出现次数。
当 right 指针向右移动时,每遇到一个新字符 ch1,如果它是第一次出现在窗口里(window[ch1] == 0),就把 ch 加 1 ,表示窗口里不同字符多了一个,然后把这个字符的出现次数在哈希表 window 里加 1 。
一旦发现 ch 大于 2 ,说明窗口里字符超了,就开始收缩窗口。把 left 指针向右移动,移除它指向的字符 ch2,也就是让 window[ch2] 减 1 ,要是减到 0 ,就把 ch 也减 1 ,表示窗口里少了一种字符。
不管怎样,都要比较当前窗口长度(right - left + 1)和已有的结果 ans,取大的更新 ans。这里的 right - left + 1 同样是因为区间的特性,要加 1 才是真正的窗口长度,C++ 里也不能马虎哦。
最后,遍历完整个字符串,返回 ans,就得到最长子串的长度啦。
通过这三种主流编程语言的代码实现,咱们可以看到,虽然语法各有不同,但核心思路都是利用滑动窗口和哈希表,通过两个指针巧妙地控制窗口的大小,实时更新字符出现的信息,从而高效地找出满足条件的最长子串。大家可以多看看,对比一下不同语言的代码风格,加深对这个算法的理解,以后遇到类似的题目就能举一反三啦!
四、复杂度分析

(一)时间复杂度
咱们这个算法的时间复杂度是 O(n),这可是相当优秀的一个指标呢!为啥能达到这么高效呢?因为在整个算法执行过程中,咱们只需对字符串进行一次从头到尾的遍历,每个字符最多也就是进出滑动窗口各一次。虽说在窗口收缩的时候,咱们还得操作哈希表,去查找和移除一些元素,但别忘了,哈希表查找、插入、删除的平均时间复杂度都是 O(1),这点操作时间和遍历整个字符串的时间比起来,简直可以忽略不计,就好像一阵微风,几乎不增加额外的时间开销。所以综合起来,不管输入的字符串有多长,咱们的算法都能稳稳地以近似线性的时间完成任务,这在处理大规模数据的时候,优势就凸显出来啦,能帮咱们节省大量的运算时间,快速得到结果。
(二)空间复杂度
再看看空间复杂度,这里是 O(1)。听起来是不是有点神奇,明明用了哈希表呀,怎么空间复杂度能这么低呢?其实奥秘就在于,哈希表在咱们这个算法里,最多就只需要存储两个不同的字符及其出现的次数。不管输入的字符串 s 变得多么庞大,哈希表占用的空间都不会跟着 “疯涨”,始终保持在一个极小的范围内,几乎可以看成是一个常量级别的空间占用。打个比方,就算字符串里有成千上万个字符,但满足题目要求的最长子串里最多就两个不同字符,哈希表也就记录这俩字符的相关信息,不会因为字符串变长就需要开辟大量新空间,所以空间复杂度稳稳地维持在 O(1),不会给计算机的内存带来太大压力,让咱们的算法在空间利用上也表现得极为出色。
五、刷题技巧与拓展

搞定这道题后,咱们可得好好总结一下其中的技巧,以后再碰到类似的字符串子串问题,就能轻松应对啦!
首先,遇到这种找满足特定条件的子串长度的题目,滑动窗口和双指针策略绝对是优先考虑的方向。就像这道题,通过巧妙地移动左右指针,让窗口灵活地在字符串上滑动,精准地框住我们想要研究的子串范围,大大减少了不必要的遍历和计算,把时间复杂度稳稳地控制在 O(n),效率超高。
其次,哈希表在处理字符统计、判断字符是否重复、记录字符出现次数这些需求的时候,简直就是 “神器”。它利用自身快速的查找、插入和删除操作,帮咱们在算法执行过程中迅速地掌握字符的动态信息,为窗口的移动和条件判断提供了坚实的依据,而且空间复杂度还能保持在 O(1),对内存相当友好。
最后,给大家留个小挑战,试试把题目条件改一改,比如说 “至多包含三个不同字符的最长子串”,看看能不能举一反三,用咱们今天学到的思路去解决。还有几道 LeetCode 上的类似题目,像 “无重复字符的最长子串”(题目链接)、“找到字符串中所有字母异位词”(题目链接),也推荐大家去做做,加深对这类问题的理解,让自己的算法功力更上一层楼!要是在刷题过程中有什么新的感悟或者疑问,欢迎随时在评论区交流分享,咱们一起抱团进步,攻克更多的算法难题!
六、总结

咱们今天深入探究了 LeetCode 上的 “至多包含两个不同字符的最长子串” 这道题,从题目含义的精准剖析,到滑动窗口解法的巧妙运用,再到代码层面的详细解读,以及复杂度的深入分析,相信大家对这类问题已经有了相当透彻的理解。滑动窗口结合哈希表的策略,能高效地在 O(n) 时间复杂度和 O(1) 空间复杂度下解决问题,这可是算法优化的经典范例。
刷题之路漫漫,每一道题都是成长的阶梯。大家在学习算法的时候,一定要多刷题、多总结,把每一道题的解法吃透,将不同的算法思路融会贯通,这样才能在面对各种千变万化的题目时,迅速找到解题的突破口。希望今天的分享能给大家的算法学习之旅带来满满的收获,如果大家在刷题过程中有什么独特的见解、巧妙的解法,或者是遇到了令人头疼的难题,都欢迎在留言区分享交流,咱们一起在算法的海洋里乘风破浪,探索更多的知识宝藏。后续我还会带来更多精彩的算法题目剖析,敬请期待,咱们下次再见!

标签:子串,字符,right,吃透,159,哈希,窗口,LeetCode,left
From: https://www.cnblogs.com/wuhailong/p/18643130

相关文章

  • 算法训练营Day28 | leetcode 122.买卖股票的最佳时机II 55.跳跃游戏 45.跳跃游戏II
    122.买卖股票的最佳时机II本题首先要清楚两点:只有一只股票!当前只有买股票或者卖股票的操作想获得利润至少要两天为一个交易单元。贪心算法这道题目可能我们只会想,选一个低的买入,再选个高的卖,再选一个低的买入…循环反复。如果想到其实最终利润是可以分解的,那么本题就......
  • leetcode 1191. K 次串联后最大子数组之和 未解决
    1191.K次串联后最大子数组之和很蠢但能通过的方法:k>=3时,算三次res。如果res2- res2==res3-res2,说明为等差数列。如果res2- res2!=res3-res2,说明循环多次的结果都是一样的。classSolution{public:intkConcatenationMaxSum(vector<int>&arr,intk)......
  • 【Leetcode_Hot100】链表
    链表160.相交链表206.反转链表234.回文链表141.环形链表142.环形链表II21.合并两个有序链表2.两数相加19.删除链表的倒数第N个结点25.K个一组翻转链表138.随机链表的复制148.排序链表23.合并K个升序链表146.LRU缓存160.相交链表方法一:模拟依......
  • 《计算机组成及汇编语言原理》阅读笔记:p133-p159
    《计算机组成及汇编语言原理》学习第11天,p133-p159总结,总计27页。一、技术总结1.segment(1)定义Broadlyspeaking,acontiguoussectionofmemory.Morespecifically,asectionofmemoryreferencedbyoneofthesegmentregistersofthe80x86family.Theme......
  • leetcode137. 只出现一次的数字 II
    题目:        给你一个整数数组 nums,除某个元素仅出现一次外,其余每个元素都恰出现三次。请你找出并返回那个只出现了一次的元素。你必须设计并实现线性时间复杂度的算法且使用常数级空间来解决此问题。示例1:输入:nums=[2,2,3,2]输出:3示例2:输入:nums=[......
  • leetcode 1749. 任意子数组和的绝对值的最大值
    1749.任意子数组和的绝对值的最大值没做出来......
  • leetcode 2606. 找到最大开销的子字符串
    2606.找到最大开销的子字符串classSolution{public:intmaximumCostSubstring(strings,stringchars,vector<int>&vals){intsize=s.size();vector<int>dp(size);autofound=chars.find(s[0]);if(found==s......
  • leetcode 213. 打家劫舍 II
    213.打家劫舍II与  198.打家劫舍  相比,多了首和尾不能同时偷的条件但是没写出来......
  • leetcode 3186. 施咒的最大总伤害
    3186.施咒的最大总伤害这道题相比 740.删除并获得点数  ,区别是这道题的元素值可以特别大,所以就不能开大数组。没做出来......
  • 攻克LeetCode 1055:探寻形成字符串的最短路径
    一、题目引入在LeetCode的题库中,1055.形成字符串的最短路径这道题饶有趣味且充满挑战。简单来说,对于给定的源字符串source和目标字符串target,我们要找出源字符串中能通过串联形成目标字符串的子序列的最小数量。如果无法通过串联源字符串中的子序列来构造目标字符串,那就得......