386 · Longest Substring with At Most K Distinct Characters最多有k个不同字符的最长子字符串(滑动窗口)

链接：LintCode 炼码 - 更高效的学习体验！

https://mp.weixin.qq.com/s?__biz=MzU2OTUyNzk1NQ==&mid=2247491103&idx=1&sn=8d9a2ed68a7dd31bb2aeb50ffe8fa4c8&source=41#wechat_redirect

题解：

class Solution { public: /** * @param s: A string * @param k: An integer * @return: An integer */ int lengthOfLongestSubstringKDistinct(string &s, int k) { // write your code here if (s.size() <= 0) { return 0; } int right = 0; int left = 0; int max_len = 0; std::unordered_map<char, int> table; while (right < s.size()) { ++table[s[right]]; if (table.size() > k) { while (left <s.size() && table.size() > k) { if (--table[s[left]] == 0) { table.erase(s[left]); } ++left; } } max_len = max(max_len, right-left+1); ++right; } return max_len; } };

class Solution { public: /** * @param s: A string * @param k: An integer * @return: An integer */ int lengthOfLongestSubstringKDistinct(string &s, int k) { // write your code here int len = s.size(); if (len <= 0) { return 0; } unordered_map<char, int> table; int j = 0; int result = INT_MIN; for (int i = 0; i < s.size(); ++i) { while (j < s.size() && table.size() <= k) { ++table[s[j]]; ++j; } if (table.size() > k) { result = max(result, j-i-1); } else if (table.size() <= k) { result = max(result, j-i); } if (--table[s[i]] == 0) { table.erase(s[i]); } } return result; } };

当while循环退出时，如果是因为table.size() > k（即插入后不同字符数超过k），那么j已经自增，指向了非法窗口的下一个位置。此时，合法的窗口应该是[i, j-2]，长度为(j-2) - i + 1 = j - i - 1。因此需要-1。

如果while退出是因为j == s.size()或插入后仍满足table.size() <= k，那么窗口[i, j-1]是合法的，长度直接为j - i。