# Problem 340: Longest Substring with At Most K Distinct Characters

> <https://leetcode.com/problems/longest-substring-with-at-most-k-distinct-characters/>

![](/files/-Lpv9zXgXngRKUqQotiD)

## 思路

* 还是利用 HashMap 和 sliding window 的方式进行
* 用 count 来记录不同的元素

```java
public class Solution {
    public int lengthOfLongestSubstringKDistinct(String s, int k) {
        int[] map = new int[128];
        int i = 0, j = 0, count = 0, maxLen = 0;
        while (j < s.length()) {
            if (map[s.charAt(j++)]++ == 0) count++;
            if (count > k) {
                while (--map[s.charAt(i++)] > 0);
                count--;
            }
            maxLen = Math.max(maxLen, j - i);
        }

        return maxLen;
    }
}
```

## Follow Up

> 如果不是求最长 length 而是直接返回最长的字符串呢？

```java
/**
 * Created by yang on 12/30/16.
 */
public class minWindow {
    public static String lengthOfLongestSubstringKDistinct(String s, int k) {
        int[] map = new int[128];
        int i = 0, j = 0, count = 0, maxLen = 0;
        String rst = "";
        while (j < s.length()) {
            if (map[s.charAt(j++)]++ == 0) count++;
            if (count > k) {
                while (--map[s.charAt(i++)] > 0) ;
                count--;
            }
            //maxLen = Math.max(maxLen, j - i );
            if (j - i > maxLen) {
                rst = s.substring(i, j);
                maxLen = Math.max(maxLen, j - i);
            }
        }

        return rst;
    }

    public static void main(String[] args) {
        String s = "bbBAbBabbbA";
        System.out.println(lengthOfLongestSubstringKDistinct(s, 2));
    }
}
```

## 易错点

1. 表达式的理解

   ```java
   if (map[s.charAt(j++)]++ == 0) count++;
   ```

   需要注意的是，**不管条件是否满足，都要完成条件里面的两次“++”**，因为这是属于条件里面的部分。也就是说，每次扫过一个元素，j 都要递增，被扫过的元素的 count 也要递增。

   ```java
   while (--map[s.charAt(i++)] > 0);
   ```

   同理，这个表达式也是一样，每次都要先减然后 i 递增。

   2.最后 j 和 i 的结束时候的情景是：i 是所选单词的开始字母，j 是所选单词的下一个字母


---

# 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://liuyang89116.gitbook.io/my-leetcode-book/chapter_2_string/sliding-window-problems/problem-340-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.