Find the longest substring with k unique characters

Problem Link

Longest Substring with K Unique Characters – GFG

Problem Statement

Given a string s consisting only of lowercase alphabets and an integer k, find the length of the longest substring that contains exactly k distinct characters.

If no such substring exists, return -1.

Examples

• Input: s = "aabacbebebe", k = 3
  Output: 7
  Explanation: The longest substring is "cbebebe" with characters 'c', 'b', and 'e'.

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

• Input: s = "aabaaab", k = 2
  Output: 7
  Explanation: The whole string contains exactly 2 unique characters: 'a' and 'b'.

Constraints

• 1 <= s.length <= 10⁵

• 1 <= k <= 26

Intuition

This problem fits the Variable Size Sliding Window with Hash Table Lookup pattern:

• We need a window where we track the number of distinct characters.

• Expand the window while the number of unique characters is ≤ k.

• When it exceeds k, shrink the window from the left until we return to exactly k distinct characters.

• Keep track of the maximum length of valid windows that have exactly k unique characters.

Approach

1. Use two pointers l and r to represent the sliding window.

2. Use a HashMap<Character, Integer> to track the frequency of characters in the current window.

3. Expand the window by moving r forward:

   • Add s[r] to the map and update its frequency.

4. While the map size > k, shrink the window from the left:

   • Decrease the frequency of s[l]

   • If frequency becomes 0, remove it from the map

   • Move l forward

5. If the map size == k, update the maxLen with the current window size.

6. After the loop ends, return maxLen if updated, else return -1.

Java Code

class Solution {
    public int longestkSubstr(String s, int k) {
        int l = 0, r = 0;
        int maxLen = -1;
        Map<Character, Integer> map = new HashMap<>();

        while (r < s.length()) {
            char ch = s.charAt(r);
            map.put(ch, map.getOrDefault(ch, 0) + 1);

            while (map.size() > k) {
                char leftChar = s.charAt(l);
                map.put(leftChar, map.get(leftChar) - 1);
                if (map.get(leftChar) == 0) {
                    map.remove(leftChar);
                }
                l++;
            }

            if (map.size() == k) {
                maxLen = Math.max(maxLen, r - l + 1);
            }

            r++;
        }

        return maxLen;
    }
}

Time and Space Complexity

• Time Complexity: O(n)
  Each character is processed at most twice (once when added, once when removed from map)

• Space Complexity: O(k)
  At most k characters are stored in the hashmap

Dry Run

Input:

s = "aabacbebebe", k = 3

Steps:

1. "aabac" → Map: {a, b, c} → Valid → Length = 5

2. "abacb" → Valid → Length = 5

3. "bacbe" → Valid → Length = 5

4. "acbeb" → Valid → Length = 5

5. "cbebebe" → Map: {c, b, e} → Valid → Length = 7 (update max)

Output: 7

Conclusion

This problem is a classic Variable Size Sliding Window with Hash Table scenario where:

• The constraint is on the number of distinct characters.

• We dynamically resize the window to maintain exactly k distinct characters.

This pattern is frequently used in problems like:

• Longest substring with at most k distinct characters

• Longest substring with all unique characters

• Minimum/maximum substring with character frequency conditions