LintCode 题解丨网易面试题：最多有k个不同字符的最长子字符串

给定字符串S，找到最多有k个不同字符的最长子串T。

在线评测地址：LintCode 领扣

样例 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;
}

}
更多题解参考：

九章算法 - 帮助更多中国人找到好工作，硅谷顶尖IT企业工程师实时在线授课为你传授面试技巧
​