【Leetcode】159. Longest Substring with At Most Two Distinct Characters

题目地址：

https://leetcode.com/problems/longest-substring-with-at-most-two-distinct-characters/

给定一个字符串$s$，求其最长的只含最多$2$种字母的子串的长度。

思路是双指针。开两个指针$j$和$i$始终保持$j\le i$，并开一个哈希表存$s[j:i]$之间每个字母出现了多少次。如果当前区间满足要求，则更新答案，继续右移$i$，否则说明当前区间含有了超过$2$种字母，此时$j$及其左边作为区间左端点一定不会有正确答案，所以右移$j$，同时更新哈希表，直到满足条件为止。代码如下：

class Solution {public:int lengthOfLongestSubstringTwoDistinct(string s) {int res = 0;// 开一个哈希表做计数，存每个字母在当前维护的窗口里出现了多少次unordered_map<char, int> mp;for (int i = 0, j = 0; i < s.size(); i++) {mp[s[i]]++;while (mp.size() > 2) {mp[s[j]]--;if (!mp[s[j]]) mp.erase(s[j]);// 计数减完了右移左指针，缩小区间j++;}res = max(res, i - j + 1);}return res;}
};

时间复杂度 O ( l s ) O(l_s) O(ls​)，空间$O(1)$（map里最多两个entry）。

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！