# Longest Substring with At Most K Distinct Characters

## 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.

**Tags**

String Two Pointers LintCode Copyright Hash Table

**Related Problems**

Medium Longest Substring Without Repeating Characters

## Analysis

窗口型two pointers的又一实例。

需要注意的是内层while循环中的跳出条件，是`!map.containsKey(ch_j) && map.size() == k`，表明在目前出现了第一个character将使得`map.size() > k`，因此break。跳出内层while循环时，`j - i`就是substring的长度，因为j指向了substring的下一个char (假设j指向substring的尾部字符，则应该用j - i + 1计算substring长度)。

## Solution

Two Pointers

```java
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;
        }
        HashMap<Character, Integer> map = new HashMap<Character, Integer>();
        int strLength = s.length();
        int i = 0;
        int j = 0;
        int ans = Integer.MIN_VALUE;

        for (i = 0; i < strLength; i++) {
            while (j < strLength) {
                char ch_j = s.charAt(j);
                if (!map.containsKey(ch_j)) {
                    if (map.size() == k) {
                        break;
                    }
                    map.put(ch_j, 1);
                } else {
                    map.put(ch_j, map.get(ch_j) + 1);
                }
                j++;
            }
            ans = Math.max(ans, j - i);
            char ch_i = s.charAt(i);
            if (map.containsKey(ch_i)) {
                if (map.get(ch_i) - 1 == 0) {
                    map.remove(ch_i);
                } else {
                    map.put(ch_i, map.get(ch_i) - 1);
                }
            }

        }

        return ans;
    }
}
```

**(Preferred Implementation)\*** **Sliding Window - Two Pointers** (16ms, 48.48%)

**O(n) time, O(n) space**

辅助HashMap存sliding window中每个distinct character的出现次数，记录元素在窗口中出现次数；

当HashMap中的元素个数大于k时，就需要移动慢指针，并且每次向前移动慢指针时，就给慢指针对应元素的计数减1，如果减为0，则remove慢指针对应元素。直到HashMap中的元素个数 == k。则继续外层循环，移动快指针，加入新的元素，或者更新原有元素的计数。

```java
class Solution {
    public int lengthOfLongestSubstringKDistinct(String s, int k) {
        if (s == null || s.length() == 0 || k == 0) {
            return 0;
        }
        HashMap<Character, Integer> count = new HashMap<>();
        int n = s.length();
        int firstIdx = 0;
        char[] chs = s.toCharArray();

        int longest = 0;

        for (int i = 0; i < n; i++) {
            count.put(chs[i], count.getOrDefault(chs[i], 0) + 1);
            while (count.size() > k) {
                count.put(chs[firstIdx], count.get(chs[firstIdx]) - 1);
                if (count.get(chs[firstIdx]) == 0) {
                    count.remove(chs[firstIdx]);
                }
                firstIdx++;
            }
            longest = Math.max(longest, i - firstIdx + 1);
        }
        return longest;
    }
}
```

## Follow Up

The interviewer may say that the string is given as a **steam**. In this situation, we can't maintain a "left pointer" as the classical O(n) hashmap solution.

\[\[<https://leetcode.com/problems/longest-substring-with-at-most-k-distinct-characters/discuss/80044/Java-O(nlogk)-using-TreeMap-to-keep-last-occurrence-Interview-"follow-up"-question!](https://leetcode.com/problems/longest-substring-with-at-most-k-distinct-characters/discuss/80044/Java-O(nlogk)-using-TreeMap-to-keep-last-occurrence-Interview-"follow-up"-question!](https://leetcode.com/problems/longest-substring-with-at-most-k-distinct-characters/discuss/80044/Java-O%28nlogk%29-using-TreeMap-to-keep-last-occurrence-Interview-"follow-up"-question!]%28https://leetcode.com/problems/longest-substring-with-at-most-k-distinct-characters/discuss/80044/Java-O%28nlogk%29-using-TreeMap-to-keep-last-occurrence-Interview-"follow-up"-question!)\\>)

Instead of recording each char's count, we keep track of char's last occurrence. If you consider k as constant, it is also a O(n) algorithm.

`inWindow` keeps track of each char in window and its last occurrence position

TreeMap + HashMap - O(nlogk)

```java
   public class Solution {
        public int lengthOfLongestSubstringKDistinct(String str, int k) {
            if (str == null || str.isEmpty() || k == 0) {
                return 0;
            }
            TreeMap<Integer, Character> lastOccurrence = new TreeMap<>();
            Map<Character, Integer> inWindow = new HashMap<>();
            int j = 0;
            int max = 1;
            for (int i = 0; i < str.length(); i++) {
                char in = str.charAt(i);
                while (inWindow.size() == k && !inWindow.containsKey(in)) {
                    int first = lastOccurrence.firstKey();
                    char out = lastOccurrence.get(first);
                    inWindow.remove(out);
                    lastOccurrence.remove(first);
                    j = first + 1;
                }
                //update or add in's position in both maps
                if (inWindow.containsKey(in)) {
                    lastOccurrence.remove(inWindow.get(in));
                }
                inWindow.put(in, i);
                lastOccurrence.put(i, in);
                max = Math.max(max, i - j + 1);
            }
            return max;
        }
    }
```

Another Implementation based on LinkedHashMap - O(n)

```java
class Solution {
    public int lengthOfLongestSubstringKDistinct(String s, int k) {
        int left = 0;
        int max = 0;
        LinkedHashMap<Character, Integer> map = new LinkedHashMap<>();
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (map.containsKey(c)) {
                map.remove(c);
            }
            map.put(c, i);
            if(map.size() > k) { 
                char key = map.keySet().iterator().next();
                left = map.get(key) + 1;
                map.remove(key);
            }
            max = Math.max(max, i - left + 1);
        }
        return max;
    }
}
```


---

# 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://aaronice.gitbook.io/lintcode/two_pointers/longest_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.