题目来源
题目描述
题目描述：给定一个字符串
s
，找出 至多 包含 k 个不同字符的最长子串
T
。
示例 1：
输入: s = “eceba”, k = 2
输出: 3
解释: 则 T 为 “ece”，所以长度为 3。
示例 2:
输入: s = “aa”, k = 1
输出: 2
解释: 则 T 为 “aa”，所以长度为 2。
class Solution {
public:
int lengthOfLongestSubstringKDistinct(string s, int k) {
std::map<char, int> map;
int left = 0, right =
}
};
题目解析
因为本题具有单调性（指针向前，种类不可能减少），所以可以用滑动窗口来做
实现
哈希表，key是字符，value是窗口内字符出现的次数。
所以m.size()就是窗口内出现的字符种类个数
class Solution {
public:
int lengthOfLongestSubstringKDistinct(string s, int k) {
int ans = 0, left = 0;
std::unordered_map<char, int> m;
for (int i = 0; i < s.size(); ++i) {
++m[s[i]];
while (m.size() > k){
if(--m[s.size()] == 0){
m.erase(s[left]);
}
++left;
}
ans = std::max(ans, i - left + 1);
}
return ans;
}
};
实现
class Solution {
public:
int lengthOfLongestSubstringKDistinct(string s, int k) {
if(k == 0){
return 0;
}
int ans = 0;
int N = s.size();
std::vector<int> count(256);
int diff = 0;
int R = 0;
for (int i = 0; i < N; ++i) {
// R 窗口的右边界
while (R < N && (diff < k || (diff == k && count[s[R]] > 0))) { //窗口内字符种类<k个 || 窗口内字符种类==k个&&边界字符之前出现过
diff += count[s[R]] == 0 ? 1 : 0;
count[s[R++]]++;
}
// R 来到违规的第一个位置
ans = std::max(ans, R - i);
diff -= count[s[i]] == 1 ? 1 : 0;
count[s[i]]--;
}
return ans;
}
};
类似题目
-
leetcode：159.最长子串（子串中所有字符种类数最多为2个） Longest Substring with At Most Two Distinct Characters
-
leetcode：340.最长子串（子串中所有字符种类数最多为k个） Longest Substring with At Most K Distinct Characters
-
leetcode：992. 最长子数组（子数组中整数种类数正好有k个）Subarrays with K Different Integers
-
leetcode：395. 最长子串（子串中每个字符次数最少应重复k次） Longest Substring with At Least K Repeating Characters
-
leetcode：3. 最长子串（子串中每个字符出现次数不可以重复） Longest Substring Without Repeating Characters
-
leetcode：239. 滑动窗口最大值（整数数组中维护一个滑动窗口，不停滑动，返回每个窗口内的最大值数组）Sliding Window Maximum