?LeetCode刷題實(shí)戰(zhàn)340：至多包含 K 個(gè)不同字符的最長(zhǎng)子串
Given a string, find the length of the longest substring T that contains at most k distinct characters.
示例
示例 1:
輸入: s = "eceba", k = 2
輸出: 3
解釋: 則 T 為 "ece"，所以長(zhǎng)度為 3。
示例 2:
輸入: s = "aa", k = 1
輸出: 2
解釋: 則 T 為 "aa"，所以長(zhǎng)度為 2。
解題
雙指針，指針中間的是可能的答案。符合要求右指針向右擴(kuò)，否則更新答案，左指針往右縮。
class Solution {
public int lengthOfLongestSubstringKDistinct(String s, int k) {
int n = s.length();
if (n < k+1) return n;
int left = 0;
int right = 0;
//K-V：K是對(duì)應(yīng)字符，V是最后一次出現(xiàn)的位置。
HashMap<Character, Integer> hashmap = new HashMap<Character, Integer>();
int max_len = 0;
while (right < n) {
//符合要求就繼續(xù)向右擴(kuò)
if (hashmap.size() < k+1){
hashmap.put(s.charAt(right), right++);
}
if (hashmap.size() == k+1) {
int index = Collections.min(hashmap.values());
hashmap.remove(s.charAt(index));
left = index + 1;
}
max_len = Math.max(max_len, right - left);
}
return max_len;
}
}