# 问题 原题链接：[https://leetcode.com/problems/longest-substring-with-at-most-k-distinct-characters/](https://leetcode.com/problems/longest-substring-with-at-most-k-distinct-characters/) Given a string, find the length of the longest substring T that contains at most k distinct characters. Example 1: ``` Input: s = "eceba", k = 2 Output: 3 Explanation: T is "ece" which its length is 3. ``` Example 2: ``` Input: s = "aa", k = 1 Output: 2 Explanation: T is "aa" which its length is 2. ``` # 分析过程 - 输入：一个字符串 - 输出：最长含有 k 个不同字符的字符串长度 - 思路：使用哈希表存储出现的次数。只含有 k 个字符就意味着哈希表最长只能是 k，扫描时保证哈希表长度是 k 即可。 # 解决方法 ```cpp class Solution { public: int lengthOfLongestSubstringKDistinct(string s, int k) { int len = (int)s.size(); if (len == 0) { return 0; } int result = 0; map<char, int> m; int begin = 0; for (int i = 0; i < len; i++) { char c = s[i]; // 当前字母出现次数+1 m[c]++; // 保证哈希表长度是2 // 如果哈希表长度大于2，则窗口的开始端就要向右移动 while (m.size() > k) { // 起始端向右移动，如果出现次数变为0就直接清除掉 char b = s[begin]; m[b]--; if (m[b] <= 0) { m.erase(b); } begin++; } // 哈希表长度是2的情况下取最大长度 result = max(result, i - begin + 1); } return result; } }; ```