# Longest Substring with K Distinct Characters

Given a string, find the length of the ** longest substring** in it

**.**

**with no more than**`K`

distinct charactersYou can assume that `K`

is less than or equal to the length of the given string.

Example 1:

```
Input: String="araaci", K=2
Output: 4
Explanation: The longest substring with no more than '2' distinct characters is "araa".
```

Example 2:

```
Input: String="araaci", K=1
Output: 2
Explanation: The longest substring with no more than '1' distinct characters is "aa".
```

```
fun maxSubArrayLen(target: Int, input: String): Int {
var maxLen = 0
var windowStart = 0
var frequencyMap = HashMap<Char, Int>()
for(windowEnd in 0 until(input.length)) {
frequencyMap[input[windowEnd]] = frequencyMap.getOrDefault(input[windowEnd], 0) + 1
while(frequencyMap.size > target) {
frequencyMap[input[windowStart]] = frequencyMap.getOrDefault(input[windowStart], 0) - 1
if(frequencyMap[input[windowStart]] == 0) {
frequencyMap.remove(input[windowStart])
}
windowStart++
}
maxLen = Math.max(maxLen, windowEnd-windowStart+1)
}
return maxLen
}
```

- First, we will insert characters from the beginning of the string until we have
`K`

distinct characters in the.**HashMap** - These characters will constitute our sliding window. We are asked to find the longest such window having no more than
`K`

distinct characters. We will remember the length of this window as the longest window so far. - After this, we will keep adding one character in the sliding window (i.e. slide the window ahead) in a stepwise fashion.
- In each step, we will try to shrink the window from the beginning if the count of distinct characters in the
is larger than**HashMap**`K`

. We will shrink the window until we have no more than`K`

distinct characters in the. This is needed as we intend to find the longest window.**HashMap** - While shrinking, we’ll decrement the character’s frequency going out of the window and remove it from the
if its frequency becomes zero.**HashMap** - At the end of each step, we’ll check if the current window length is the longest so far, and if so, remember its length.