## Problem Statement

Given a string, find the length of the longest possible substring in it that has exactly `K`

distinct characters. If there is no possible substring then print -1.

You can assume that `K`

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

**Example 1:**

```
Input: S = "aabacbebebe", K = 3
Output: 7
Explanation: "cbebebe" is the longest substring with 3 distinct characters.
```

**Example 2:**

```
Input:
S = "aaaa", K = 2
Output: -1
Explanation: There's no substring with 2 distinct characters.
```

## Solution

This problem is based on the variable-size sliding window pattern. We have already solved a similar problem Smallest Subarray with a given Sum using this pattern. We will use the same strategy to solve this problem as well.

- Consider each substring as a sliding window.
- Start with a sliding window of size
`1`

(`windowStart=0, windowEnd=0`

). - Initialize a
**HashMap**that stores the character count for each character in the current window. - Iterate over the string and insert new characters in the HashMap until we have exactly
`K`

distinct characters in the HashMap.- At this point, we have a window (subarray) that conforms to our criteria of having exactly
`K`

unique characters. So remember the length of this window as the longest window so far. - However, if the count of distinct characters in the HashMap is greater than
`K`

, then we will start shrinking the window from the left until the count becomes smaller than or equal to`K`

. To shrink the window, we will need to discard the leftmost element of the window from the HashMap.

- At this point, we have a window (subarray) that conforms to our criteria of having exactly

```
import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;
class LongestSubstringWithKUniqueCharacters {
private static int findLengthOfLongestSubstringWithKUniqueCharacters(String s, int k) {
int n = s.length();
int maxLen = -1; // Stores the length of the longest substring with k unique characters found so far.
Map<Character, Integer> windowCharCount = new HashMap<>(); // Stores the character count for each character in the current window
int windowStart = 0;
for(int windowEnd = 0; windowEnd < n; windowEnd++) {
// Add the next character to the sliding window
char c = s.charAt(windowEnd);
windowCharCount.put(c, windowCharCount.getOrDefault(c, 0) + 1);
// Shrink the sliding window, until we have exactly 'k' distinct characters in the window
while(windowCharCount.size() > k) {
char leftChar = s.charAt(windowStart);
// Discard the character at windowStart since we're gonna move it out of the window now.
windowCharCount.put(leftChar, windowCharCount.get(leftChar) - 1);
if(windowCharCount.get(leftChar) == 0) {
windowCharCount.remove(leftChar);
}
windowStart++; // Shrink the window
}
if(windowCharCount.size() == k) {
// Update maximum length found so far
maxLen = Math.max(maxLen, windowEnd-windowStart+1);
}
}
return maxLen;
}
public static void main(String[] args) {
Scanner keyboard = new Scanner(System.in);
String s = keyboard.next();
int k = keyboard.nextInt();
keyboard.close();
System.out.printf("Longest substring with %d unique characters = %d%n", k, findLengthOfLongestSubstringWithKUniqueCharacters(s, k));
}
}
```