Longest Substring with At Most K Distinct Characters 386
Question
Given a string s, find the length of the longest substring T that contains at most k distinct characters.
Example
For example, Given s = "eceba", k = 3,
T is "eceb" which its length is 4.
Challenge
O(n), n is the size of the string s.
Solution
用双指针解题。用一个hashmap记录遇到的字符及其出现次数。
指针left和right都从0开始,right向后遍历数组。
当right遇到字符是之前出现过的,则直接在hashmap中将其数量加1;若right遇到字符是之前没有出现过的,则分情况讨论1)若目前遇到过字符种类不足k个,则直接加入;2)若目前遇到过的字符种类大于k个,则移动左边界减少字符,直到字符种类少于k个后再加入。
每次改变左边界时更新max的值。但是最后一次当right到数组尾部时,这一次不会改变左边界,所以要在循环结束后最后一次更新max。
代码如下:
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) {
// write your code here
if(s == null || s.length() == 0 || k == 0){
return 0;
}
if(s.length() <= k){
return s.length();
}
HashMap<Character, Integer> map = new HashMap<Character, Integer>();
int left = 0;
int right = 0;
int max = 0;
while(right < s.length()){
//如果遇到的字符是之前出现过的,则直接将其数量加1
if(map.containsKey(s.charAt(right))){
map.put(s.charAt(right), map.get(s.charAt(right)) + 1);
}else{
//如果遇到的新字符之前没有出现过则分情况讨论
//若目前遇到过字符种类不足k个,则直接加入
if(map.size() < k){
map.put(s.charAt(right), 1);
}else{
//若目前遇到过的字符种类大于k个,则移动左边界减少字符,直到字符种类少于k个后再加入
max = Math.max(max, right - left);
while(map.size() >= k){
map.put(s.charAt(left), map.get(s.charAt(left)) - 1);
if(map.get(s.charAt(left)) == 0){
map.remove(s.charAt(left));
}
left++;
}
map.put(s.charAt(right), 1);
}
}
right++;
}
//right到底之后要统计最后一次substring的长度
max = Math.max(max, right - left);
return max;
}
}