当前位置：网站首页>leetcode：159.最多有两个不同字符的最长子串

leetcode：159.最多有两个不同字符的最长子串

2022-08-10 16:39:00 【OceanStar的学习笔记】

题目来源

leetcode：159-VIP.最多有两个不同字符的最长子串

题目描述

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

示例 1:

输入: “eceba”
输出: 3
解释: t 是 “ece”，长度为3。
示例 2:

输入: “ccaabbb”
输出: 5
解释: t 是 “aabbb”，长度为5。

class Solution {
    
public:
    int lengthOfLongestSubstringTwoDistinct(string s) {
    

    }
};

题目解析

思路

用一个map，key为字符，value为字符出现次数。
如果map的映射数量超过2个的时候，就删除一个映射
- 比如此时 HashMap 中e有2个，c有1个，此时把b也存入了 HashMap，那么就有三对映射了
- 这时 left 是0，先从e开始，映射值减1，此时e还有1个，不删除，left 自增1
- 这时 HashMap 里还有三对映射，此时 left 是1，那么到c了，映射值减1，此时e映射为0，将e从 HashMap 中删除，left 自增1
然后更新结果为 i - left + 1，以此类推直至遍历完整个字符串

class Solution {
    
public:
    int lengthOfLongestSubstringTwoDistinct(string s) {
    
        int res = 0, left = 0;
        unordered_map<char, int> m;
        for (int i = 0; i < s.size(); ++i) {
    
            ++m[s[i]];
            while (m.size() > 2) {
    
                if (--m[s[left]] == 0) m.erase(s[left]);
                ++left;
            }
            res = max(res, i - left + 1);
        }
        return res;
    }
};

思路

用一个map，key为字符，value为字符最新的坐标
- 比如题目中的例子 “eceba”，遇到第一个e，映射其坐标0，遇到c，映射其坐标1，遇到第二个e时，映射其坐标2，当遇到b时，映射其坐标3
如果map的映射数量超过2个的时候，就删除一个映射
- 从left开始往右找，看每个字符在map中的映射值是否等于当前left（）
- 比如第一个e，HashMap 此时映射值为2，不等于 left 的0，那么 left 自增1，遇到c的时候，HashMap 中c的映射值是1，和此时的 left 相同，那么我们把c删掉，left 自增1，再更新结果

class Solution {
    
public:
    int lengthOfLongestSubstringTwoDistinct(string s) {
    
        int res = 0, left = 0;
        unordered_map<char, int> m;
        for (int i = 0; i < s.size(); ++i) {
    
            m[s[i]] = i;
            while (m.size() > 2) {
    
                if (m[s[left]] == left) m.erase(s[left]);
                ++left;
            }
            res = max(res, i - left + 1);
        }
        return res;
    }
};