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

链接LintCode 炼码 - 更高效的学习体验https://mp.weixin.qq.com/s?__bizMzU2OTUyNzk1NQmid2247491103idx1sn8d9a2ed68a7dd31bb2aeb50ffe8fa4c8source41#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_mapchar, 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-left1); 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_mapchar, 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。