340. Longest Substring with At Most K Distinct Characters

Given a string, find the length of the longest substring T that contains at most k distinct characters.

For example, Given s = “eceba” and k = 2,

T is "ece" which its length is 3.

本题和Longest Substring with At Most Two Distinct Characters很类似，代码如下：

 1 public class Solution {
 2     public int lengthOfLongestSubstringKDistinct(String s, int k) {
 3         int len = 0;
 4         int lo = 0;
 5         int hi = 0;
 6         if(s.length()==0) return len;
 7         Map<Character,Integer> map = new HashMap<>();
 8         while(hi<s.length()){
 9             if(map.size()<=k){
10                 char c = s.charAt(hi);
11                 map.put(c,hi);
12                 hi++;
13             }
14             if(map.size()>k){
15                 int leftmost = s.length();
16                 for(int i:map.values()){
17                     leftmost= Math.min(leftmost,i);
18                 }
19                 char c = s.charAt(leftmost);
20                 map.remove(c);
21                 lo = leftmost+1;
22             }
23             len = Math.max(len,hi-lo);
24         }
25         return len;
26     }
27 }