Problem

Given a string, find the longest substring that contains only k unique or distinct characters.

Examples

Example 1:

1
2
3

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

Example 2:

1
2
3

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

Solutions

Method 1 - Brute Force

If the length of string is n, then there can be n*(n+1)/2 possible substrings. A simple way is to generate all the substring and check each one whether it has exactly k unique characters or not. If we apply this brute force, it would take O(n^2) to generate all substrings and O(n) to do a check on each one. Thus overall it would go O(n^3).

We can further improve this solution by creating a hash table and while generating the substrings, check the number of unique characters using that hash table. Thus it would improve up to O(n^2).

Method 2 - Sliding Window with Frequency Hashmap

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

  • Start with a sliding window of size 1 (left=0, right=0). We expand window with right, and shrink it by moving left
  • Use a map to store frequency 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.
    • Iterate through the string, expanding the window by adding characters until we have exactly K distinct characters in the HashMap (representing the current longest substring with K unique characters).
    • If the window contains more than K distinct characters, shrink it from the left by removing the leftmost element from the HashMap, continuing until we have K or fewer distinct characters.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

class Solution {

	private int lengthOfLongestSubstringWithKUniqChars(String s, int k) {
		int n = s.length();
		// answer - length of longest substring with k uniq chars
		int ans = -1;
		// frequency map of chars in window
		Map<Character, Integer> windowCharCnt = new HashMap<>();
		int left = 0; // left = start of window, right end of window
		for (int right = 0; right < n; right++) {
			char c = s.charAt(right);
			
			windowCharCnt.put(c, windowCharCnt.getOrDefault(c, 0) + 1);

			// Shrink the sliding window
			// until we have exactly 'k' distinct characters in the window
			while (windowCharCnt.size() > k) {
				char leftChar = s.charAt(left);

				windowCharCnt.put(leftChar, windowCharCnt.get(leftChar) - 1);

				if (windowCharCnt.get(leftChar) == 0) {
					windowCharCnt.remove(leftChar);
				}

				left++;
			}

			if (windowCharCnt.size() == k) {
				ans = Math.max(ans, right - left + 1);
			}
		}

		return ans;
	}
}

Complexity

  • ⏰ Time complexity: O(n)
  • 🧺 Space complexity: O(n)