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.
Comments
Post a Comment
Leave Comment