386.Longest Substring with At Most K Distinct Characters

1.Description(Medium)

Given a strings, 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 is4.

Challenge

O(n), n is the size of the strings.

Tags

Two Pointers Hash Table String LintCode Copyright

2.Code

http://blog.csdn.net/whuwangyi/article/details/42451289

http://www.cnblogs.com/grandyang/p/5185561.html

http://www.cnblogs.com/grandyang/p/5351347.html

Version 1: hashmap里记录char和char出现的次数。

用哈希表来做，哈希表记录每个字符的出现次数

Given S = “eceba”,k=2

T is “ece” which its length is 3.

然后如果哈希表中的映射数量超过k个的时候，我们需要删掉一个映射，比如此时哈希表中e有2个，c有1个，此时把b也存入了哈希表，那么就有三对映射了，这时我们的left是0，先从e开始，映射值减1，此时e还有1个，不删除，left自增1。这是哈希表里还有三对映射，此时left是1，那么到c了，映射值减1，此时e映射为0，将e从哈希表中删除，left自增1，

然后我们更新结果为i - left + 1，(每次遍历一个char的时候都更新)

以此类推直至遍历完整个字符串，

public int lengthOfLongestSubstringKDistinct(String s, int k) {
        if(s==null || s.length()==0 || k<=0){
            return 0;
        }
        HashMap<Character,Integer> map=new HashMap<>();
        int maxlen=0;
        int start=0;
        for(int i=0;i<s.length();i++){
            char current=s.charAt(i);
            if(map.containsKey(current)){
                map.put(current,map.get(current)+1);
            }
            else{
                map.put(current,1);
                while(map.size()>k){
                    char left=s.charAt(start);
                    int count=map.get(left);
                    if(count>1){
                        map.put(left, count-1);
                    }else{
                        map.remove(left);
                    }
                    start++;
                }
            }
            maxlen=Math.max(maxlen, i-start+1);
        }
        return maxlen;
    }

Version 2: hashmap 存放的是char和最后出现的坐标。

我们还可以映射每个字符最新的坐标，比如题目中的例子"eceba"，遇到第一个e，映射其坐标0，遇到c，映射其坐标1，遇到第二个e时，映射其坐标2，当遇到b时，映射其坐标3，每次我们都判断当前哈希表中的映射数，如果大于k的时候，那么我们需要删掉一个映射，我们还是从left=0时开始向右找，

我们看每个字符在哈希表中的映射值是否等于当前坐标left，

比如第一个e，哈希表此时映射值为2，不等于left的0，

那么left自增1，遇到c的时候，哈希表中c的映射值是1，和此时的left相同，那么我们把c删掉，left自增1，再更新结果，以此类推直至遍历完整个字符串，

public int lengthOfLongestSubstringKDistinct2(String s, int k){
        if(s==null || s.length()==0 || k<=0){
            return 0;
        }
        HashMap<Character,Integer> map=new HashMap<>();
        int maxlen=0;
        int start=0;
        for(int i=0;i<s.length();i++){
            char current=s.charAt(i);
            if(map.containsKey(current)){
                map.put(current, i);
            }else{
                map.put(current,i);
                while(map.size()>k){
                    char left=s.charAt(start);
                    if(map.get(left)!=start){
                        start++;
                    }else{
                        map.remove(left);
                        start++;
                    }
                }
            }
            maxlen=Math.max(maxlen, i-start+1);
        }
        return maxlen;
    }