解
第一步丈冬，萬年不變的查錯甘畅。如果給的string是null或長度為0疏唾，那么直接return。
public int lengthOfLongestSubstringKDistinct(String s, int k) {
if (s == null || s.length() == 0 || k == 0) {
return 0;
}
...
}
思路跟之前的幾道題很像喉童，就是two pointer遍歷堂氯。題目要求最多有k個unique的字符露氮，那就用個HashMap存一下出現(xiàn)過的字符，和出現(xiàn)過的次數(shù)。所以先做一下初始化叁扫。
int j = 0;
int maxLength = 0;
Map<Character, Integer> hash = new HashMap<>();
然后一個for循環(huán)做第一個pointer畜埋，while循壞做第二個pointer悠鞍。
for (int i = 0; i < s.length(); i++) {
while (j < s.length() && hash.size() <= k) {
...
}
}
怎樣知道有沒有k個unique的字符呢？就是HashMap的size掩宜，一共有多少個key。如果到了k個辽旋，而且新的字符出現(xiàn)补胚，那就停下來追迟。
if (hash.size() == k && !hash.containsKey(s.charAt(j))) {
break;
}
如果不到k個敦间，那就把當前的這個放到hash里面，并且出現(xiàn)的次數(shù)+1金闽。然后移動第二個pointer到下一個前向移動剿骨。
hash.put(s.charAt(j), hash.getOrDefault(s.charAt(j), 0) + 1);
j++;
這樣while循環(huán)就結(jié)束了浓利。這時候只有可能出現(xiàn)兩種情況。
- j到了s的結(jié)尾嫡秕，值為
s.length() - 找到了k個unique的字符昆咽，并且如果加入當前字符牙甫，就會超過k個。
不管是哪種情況泻轰，都代表著且轨，以s.charAt(i)開頭的substring，已經(jīng)到了unique字符總數(shù)小于等于k的最大長度泳挥。所以更新一下最大長度。
maxLength = Math.max(maxLength, j - i);
然后玷过，以i開頭的找完了筑煮，就把s.charAt(i)刪掉，讓for循環(huán)把i往前移真仲，然后繼續(xù)找以i+1開頭的最大長度。把當前字符刪掉虑凛，就需要找到當前總共的個數(shù)桑谍，去掉一個祸挪，然后去掉后是0，那么就代表著這個字符不存在于新的substring里了雹仿，所以就需要從HashMap里面刪掉整個key胧辽，這樣才不會影響一開始的Hashmap.size()公黑。
int currentCount = hash.get(s.charAt(i)) - 1;
if (currentCount == 0) {
hash.remove(s.charAt(i));
} else {
hash.put(s.charAt(i), currentCount);
}
最后整個for循環(huán)完成凡蚜，返回最大長度。（小優(yōu)化：對比當前剩余字符串的長度和最大長度。如果最大長度超過剩余的長度，就直接返回蝉绷。因為剩下的就算全部算上熔吗，也不可能超過最大長度桅狠。）
return maxLength;
完整的code
public class Solution {
/*
* @param s: A string
* @param k: An integer
* @return: An integer
*/
public int lengthOfLongestSubstringKDistinct(String s, int k) {
if (s == null || s.length() == 0 || k == 0) {
return 0;
}
int j = 0;
int maxLength = 0;
Map<Character, Integer> hash = new HashMap<>();
for (int i = 0; i < s.length(); i++) {
while (j < s.length() && hash.size() <= k) {
if (hash.size() == k && !hash.containsKey(s.charAt(j))) {
break;
}
hash.put(s.charAt(j), hash.getOrDefault(s.charAt(j), 0) + 1);
j++;
}
maxLength = Math.max(maxLength, j - i);
int currentCount = hash.get(s.charAt(i)) - 1;
if (currentCount == 0) {
hash.remove(s.charAt(i));
} else {
hash.put(s.charAt(i), currentCount);
}
}
return maxLength;
}
}
分析
減了一個map中跌，空間占用O(n)漩符，n為s的長度（字符數(shù)）驱还。因為最壞情況就是每個字符都放進map里面。時間是O(n)闷沥，因為兩個pointer舆逃，都最多遍歷s各一次疟丙，加起來就是O(2n)，也就是O(n)览祖。
這道題不難炊琉，延續(xù)了two pointer的優(yōu)化解法，即一個for loop锰悼，一個while loop箕般，j不隨著i的變化而重置舔清，繼而達到O(n)的復(fù)雜度曲初，而不是O(n2)臼婆。HashMap的去重來數(shù)有多少個字符幌绍，很容易想到傀广，支持的加入和刪除，也是可以輕易想到的奖唯。隨意總的來說糜值，這題不難。
