> For the complete documentation index, see [llms.txt](https://mayanktyagi3111.gitbook.io/interview-prep/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://mayanktyagi3111.gitbook.io/interview-prep/hashmap-and-hashset-and-sliding-window/longest-substring-with-at-most-k-distinct-characters.md).

# Longest Substring with At Most K Distinct Characters

Given a string *S*, find the length of the longest substring *T* that contains at most k distinct characters.

#### Example

**Example 1:**

```
Input: S = "eceba" and k = 3
Output: 4
Explanation: T = "eceb"
```

**Example 2:**

```
Input: S = "WORLD" and k = 4
Output: 4
Explanation: T = "WORL" or "ORLD"
```

#### Challenge

O(n) time

```java
class Solution {
    public int lengthOfLongestSubstringKDistinct(String str, int k) {
        if (k == 0 || str.length() == 0)
            return 0;
        HashMap<Character, Integer> map = new HashMap<>();
        int start = 0, unique = 0;
        int maxLen = 0;
        for (int i = 0; i < str.length(); i++) {
            char x = str.charAt(i);
            if (!map.containsKey(x) || map.get(x) == 0)
                unique++;
            map.put(x, map.getOrDefault(x, 0) + 1);
            // Removing characters from start of our window until the number
            // of unique chars > K
            while (unique > k) {
                map.put(str.charAt(start), map.get(str.charAt(start)) - 1);
                if (map.get(str.charAt(start)) == 0) {
                    map.remove(str.charAt(start));
                    unique--;
                }
                start++;
            }
            maxLen = Math.max(maxLen, i - start + 1);
        }
        return maxLen;
    }
}
```