题目来源

• leetcode：340-VIP.至多包含K个不同字符的最长子串

题目描述

题目描述：给定一个字符串 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.最多有两个不同字符的最长子串 Longest Substring with At Most Two Distinct Characters

• leetcode：340.至多包含K个不同字符的最长子串 Longest Substring with At Most K Distinct Characters

• [LeetCode] 3. 最长无重复字符的子串 Longest Substring Without Repeating Characters

• [LeetCode] 239. 滑动窗口最大值Sliding Window Maximum