# 386.Longest Substring with At Most K Distinct Characters

## 1.Description(Medium)

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**](https://www.lintcode.com/en/problem/longest-substring-with-at-most-k-distinct-characters/#challenge)

O(n), n is the size of the string*s*.

[**Tags**](https://www.lintcode.com/en/problem/longest-substring-with-at-most-k-distinct-characters/#tags)

[Two Pointers](https://www.lintcode.com/tag/two-pointers/) [Hash Table](https://www.lintcode.com/tag/hash-table/) [String](https://www.lintcode.com/tag/string/) [LintCode Copyright](https://www.lintcode.com/tag/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;
    }
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://junnie.gitbook.io/amazon-mock-interview/onsite-ii/386longest-substring-with-at-most-k-distinct-characters.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.