# 1. Introduction

In this blog post, we will explore a common problem in string processing: finding the longest substring with exactly K distinct characters. This is a variant of the sliding window technique and is useful in various applications, including text processing and data analysis.

## Problem

Given a string, find the length of the longest possible substring that has exactly K distinct characters. If there is no possible substring, then print -1.

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.

# 2. Solution Steps

1. Use a sliding window approach to process the string.

2. Use a hashmap to keep track of the counts of characters in the current window.

3. Expand the window and add characters until we have K distinct characters.

4. Once we exceed K distinct characters, shrink the window from the left.

5. Update the maximum length whenever we have exactly K distinct characters in the window.

6. Return the maximum length found, or -1 if no such substring exists.

# 3. Code Program

``````import java.util.HashMap;

public class Solution {

// Main method for testing
public static void main(String[] args) {
System.out.println("Length of longest substring: " + longestSubstringKDistinct("aabacbebebe", 3));
System.out.println("Length of longest substring: " + longestSubstringKDistinct("aaaa", 2));
}

// Method to find the longest substring with K distinct characters
public static int longestSubstringKDistinct(String s, int K) {
HashMap<Character, Integer> charFrequencyMap = new HashMap<>();
int windowStart = 0, maxLength = -1;

for (int windowEnd = 0; windowEnd < s.length(); windowEnd++) {
char rightChar = s.charAt(windowEnd);
charFrequencyMap.put(rightChar, charFrequencyMap.getOrDefault(rightChar, 0) + 1);

// Shrink the sliding window, until we are left with 'K' distinct characters in the frequency map
while (charFrequencyMap.size() > K) {
char leftChar = s.charAt(windowStart);
charFrequencyMap.put(leftChar, charFrequencyMap.get(leftChar) - 1);
if (charFrequencyMap.get(leftChar) == 0) {
charFrequencyMap.remove(leftChar);
}
windowStart++;
}

// Update the maximum length
if (charFrequencyMap.size() == K) {
maxLength = Math.max(maxLength, windowEnd - windowStart + 1);
}
}
return maxLength;
}
}
``````

### Output:

```Length of longest substring: 7
Length of longest substring: -1
```

### Explanation:

The longestSubstringKDistinct method uses the sliding window technique with a hashmap to find the longest substring with exactly K distinct characters.

For example, in the string "aabacbebebe" with K = 3, the longest substring is "cbebebe", which has a length of 7.

In the second example, "aaaa" does not contain any substring with 2 distinct characters, resulting in an output of -1.