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

tech2022-08-18  137

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

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

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

方法1: 主要思路: (1)使用滑动窗口,加哈希统计; (2)当统计的元素数量是3时,需要减小窗口内的元素, 直到元素的数量再次达到2,停止;

class Solution { public: int lengthOfLongestSubstringTwoDistinct(string s) { //特殊的情形直接返回 if(s.size()<3){ return s.size(); } int count=0;//统计长度 //滑动窗口的左右边界 int left=0; int right=0; //统计元素的数量 unordered_map<char,int>mp; while(right<s.size()){ ++mp[s[right]];//统计元素 //当统计到的元素的种类到了三个时,要减小 窗口 if(mp.size()==3){ //先保存当前可能的更大的窗口 count=max(count,right-left); //减小窗口 while(mp.size()==3){ --mp[s[left]]; if(mp[s[left]]==0){//当窗口减小的过程中,某个元素的数量减小到0时,删除此类元素的统计 mp.erase(s[left]); } ++left;//调整窗口的左边界 } } ++right;//调整窗口的右边界 } return max(count,right-left); } };
最新回复(0)