给定字符串S，找到最多有k个不同字符的最长子串T。
在线做题地址
样例 1:
输入: S = "eceba" 并且 k = 3
输出: 4
解释: T = "eceb"
样例 2:
输入: S = "WORLD" 并且 k = 4
输出: 4
解释: T = "WORL" 或 "ORLD"
算法：同向双指针 + 哈希表
通过使用同向双指针的算法，我们可以做到一次遍历字符串就得到答案。 在字符串上移动滑动窗口，保证窗口内有不超过 k 个不同字符，同时在每一步更新最大子串长度。
如果字符串为空或者 k 是零的话返回 0。设置指针为字符串开头 left = 0 和 right = 0，初始化最大子串长度 maxLen = 1。当 right < N 时： - 将当前字符 s[right] 加入哈希表并且向右移动 right 指针。 - 如果哈希表包含 k + 1 个不同字符，在哈希表中移去最左出现的字符(s[left])，右移动 left 指针使得滑动窗口只包含 k 个不同字符。 - 更新 maxLen = max(maxLen, right - left)。
复杂度分析
时间复杂度O(n) - 只用扫描一遍字符串，复杂度即字符串的长度空间复杂度O(kind) - 只用开一个数组记录各种不同的字符
public class Solution {
/**
* @param s: A string
* @param k: An integer
* @return: An integer
*/
public int lengthOfLongestSubstringKDistinct(String s, int k) {
if (s.length() == 0 || k == 0) {
return 0;
}
int left = 0, right = 0, cnt = 0;
int charSet[] = new int[256];
int ans = 0;
while (right < s.length()) {
// 统计right指向的字符
// 当字符在窗口内第一次出现时，字符种类数+1，该字符出现次数+1
if (charSet[s.charAt(right)] == 0) {
cnt++;
}
charSet[s.charAt(right)]++;
right++;
// 向右移动left，保持窗口内只有k种不同的字符
while (cnt > k) {
charSet[s.charAt(left)]--;
// 当该字符在本窗口不再出现时，字符种类数-1
if (charSet[s.charAt(left)] == 0) {
cnt--;
}
left++;
}
// 更新答案
ans = Math.max(ans, right - left);
}
return ans;
}
}
更多题解参考
