# LeetCode 340. Longest Substring with At Most K Distinct Characters

## 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 = 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`

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