给定字符串 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;     }  } 

点此查看更多题解