## Description

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

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 = 2Output:3Explanation:The substring is "ece" with length 3.

**Example 2:**

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

**Constraints:**

`1 <= s.length <= 5 * 10`

^{4}`0 <= k <= 50`

## Explanation

Use the sliding window technique. Pointer j moves faster, pointer i moves slower. Keep moving the right pointer j and record the s[j] characters into the hashmap. When the hashmap has k + 1 distinct character, remove the s[i] character from the map and move i right to one position so that the sliding window contains only k distinct characters.

## Python Solution

```
class Solution:
def lengthOfLongestSubstringKDistinct(self, s: str, k: int) -> int:
max_length = 0
visited = {}
i = 0
j = 0
while j < len(s):
visited[s[j]] = visited.get(s[j], 0) + 1
if len(visited) > k:
max_length = max(max_length, j - i)
while len(visited) > k:
visited[s[i]] -= 1
if visited[s[i]] == 0:
del visited[s[i]]
i += 1
j += 1
return max(max_length, len(s) - i)
```

- Time Complexity: O(N).
- Space Complexity: O(N).