Longest Substring With K Distinct Characters - Java Solution

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.