# Longest Substring with K Unique Characters

``````例如，给定 s = "eceba" , k = 3,
T 是 "eceb"，长度为 4.
``````

``````O(n), n 是所给字符串的长度
``````

## Solution

start和end是当前字符串的起始和终止index。

## Code

``````public class Solution {
/**
* @param s : A string
* @return : The length of the longest substring
*           that contains at most k distinct characters.
*/
public int lengthOfLongestSubstringKDistinct(String s, int k) {
if (s == null || s.length() == 0 || k <= 0) {
return 0;
}
int start = 0;
int res = 1;
Map<Character, Integer> map = new HashMap<Character, Integer>();
map.put(s.charAt(0), 1);
for (int end = 1; end < s.length(); end++) {
char ch = s.charAt(end);
if (map.containsKey(ch)) {
map.put(ch, map.get(ch)+1);
} else {
if (map.size() == k) {
res = Math.max(res, end - start);
//full map, need to remove the first character in ths substring
for (int index = start; index < end; index++) {
map.put(s.charAt(index), map.get(s.charAt(index))-1);
start++;
if (map.get(s.charAt(index)) == 0) {
//have removed all occurance of a char
map.remove(s.charAt(index));
break;
}
}
}
map.put(ch, 1);
}
}
res = Math.max(res, s.length() - start);
return res;
}
}

``````