# 0340. Longest Substring with At Most K Distinct Characters

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

## Description

Given a string `s` and an integer `k`, return *the length of the longest substring of* `s` *that contains at most* `k` ***distinct** characters*.

**Example 1:**

```
**Input:** s = "eceba", k = 2
**Output:** 3
**Explanation:** The substring is "ece" with length 3.
```

**Example 2:**

```
**Input:** s = "aa", k = 1
**Output:** 2
**Explanation:** The substring is "aa" with length 2.
```

**Constraints:**

* `1 <= s.length <= 5 * 104`
* `0 <= k <= 50`

## ac: window problem in string

```java
class Solution {
    public int lengthOfLongestSubstringKDistinct(String s, int k) {
        // edge cases
        if (s == null || s.length() == 0 || k <= 0) return 0;

        // build note
        Map<Character, Integer> map = new HashMap<Character, Integer>();
        int l = 0, r = 0, lgst = 0, cnt = 0;

        // iterate
        for (; r < s.length(); r++) {
            char c = s.charAt(r);
            map.put(c, map.getOrDefault(c, 0) + 1);
            if (map.get(c) == 1) cnt++;  // new character appear in current window

            while (cnt > k) {  // one window formed
                lgst = Math.max(lgst, r - l);  // store length
                char lc = s.charAt(l);
                map.put(lc, map.get(lc) - 1);
                l++;  // remove left char, move window

                if (map.get(lc) == 0) cnt--;  // reduce one char count 
            }
        }
        lgst = Math.max(lgst, r - l);  // update last window value

        // result
        return lgst;
    }
}
```
