给定字符串S,找到最多有k个不同字符的最长子串T。
样例 1:
输入: S = "eceba" 并且 k = 3
输出: 4
解释: T = "eceb"
样例 2:
输入: S = "WORLD" 并且 k = 4
输出: 4
解释: T = "WORL" 或 "ORLD"
挑战
O(n) 时间复杂度
class Solution {
public:
int lengthOfLongestSubstringKDistinct(string &s, int k) {
// write your code here
int i = 0, j = 0, MAX = 0, n = s.size(), count = 0;
unordered_map<char,int> m;
char ch;
for( ; j < n; j++)
{
ch = s[j];
if (m[ch] == 0) //右端点有新的字符
count++;
m[ch]++;
if(count > k) //字符种类超了
{
ch = s[i++];
m[ch]--;
if(m[ch] == 0)
count--;//如果为0,种类减少
}
MAX = j-i+1;//MAX只增不减,是最后的答案
}
return MAX;
}
};
100% 数据通过测试 总耗时 302 ms 您的提交打败了 41.40% 的提交!