Logo

Kode$word

Longest Substring with K Unique Characters – Efficient Sliding Window Solution
Longest Substring with K Unique Characters – Efficient Sliding Window Solution

Longest Substring with K Unique Characters – Efficient Sliding Window Solution

Master the sliding window technique using HashMap to find the longest substring with exactly K distinct characters.

6 views
0
0
SlidingWindowHashMapStringsGFG
Github icon

Introduction

Finding substrings with unique characters is a common problem in string manipulation and interview questions.

GFG’s Longest Substring with K Unique Characters problem challenges you to find the length of the longest substring containing exactly K distinct characters.

The focus is not just on brute-force solutions, but on using sliding window with a HashMap to efficiently track character frequencies and window boundaries.

If you’d like to try solving the problem first, you can attempt it here:

Try the problem on GeeksforGeeks:

https://leetcode.com/problems/max-consecutive-ones-iii/


Problem Understanding

You are given:

  1. A string s of lowercase letters
  2. An integer k

Your task: Return the length of the longest substring containing exactly k distinct characters.

Examples:

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

Input: s = "aaaa", k = 2
Output: -1
Explanation: No substring contains exactly 2 distinct characters.

Input: s = "aabaaab", k = 2
Output: 7
Explanation: "aabaaab" has exactly 2 unique characters.


A naive approach would try all possible substrings, count unique characters, and track the max length.

  1. Time Complexity: O(n²)
  2. Inefficient for large strings


Key Idea: Sliding Window + HashMap

Instead of recomputing the unique characters for every substring:

  1. Use a HashMap to store character frequencies in the current window
  2. Use two pointers (i and j) to maintain the window
  3. Expand the window by moving j and add characters to the map
  4. Shrink the window from the left when the number of unique characters exceeds k
  5. Update the max length whenever the window has exactly k unique characters

This ensures each character is processed only once, giving a linear solution.


Approach (Step-by-Step)

  1. Initialize a HashMap mp to store character counts
  2. Use two pointers i (window start) and j (window end)
  3. Iterate over the string with j
  4. Add s[j] to the map and update its count
  5. Check the map size:
  6. If size < k → move j forward
  7. If size == k → update max length, move j forward
  8. If size > k → shrink window from i until map size <= k
  9. After iterating, return max (or -1 if no valid substring exists)

Optimization:

  1. Using a HashMap avoids recalculating the number of unique characters for every substring
  2. Sliding window ensures O(n) complexity


Implementation (Java)

class Solution {
public int longestKSubstr(String s, int k) {
HashMap<Character,Integer> mp = new HashMap<>();
int i = 0, j = 0;
int max = -1;

while (j < s.length()) {
// Add current character to map
mp.put(s.charAt(j), mp.getOrDefault(s.charAt(j), 0) + 1);

if (mp.size() < k) {
j++;
}
else if (mp.size() == k) {
// Update max length when exactly k unique characters
max = Math.max(max, j - i + 1);
j++;
}
else {
// Shrink window until map size <= k
while (mp.size() > k) {
mp.put(s.charAt(i), mp.get(s.charAt(i)) - 1);
if (mp.get(s.charAt(i)) == 0) {
mp.remove(s.charAt(i));
}
i++;
}
max = Math.max(max, j - i + 1);
j++;
}
}
return max;
}
}


Dry Run Example

Input:

s = "aabacbebebe", k = 3

Execution:

  1. Window [0-4] = "aaba" → unique = 2 → continue
  2. Window [1-6] = "abacb" → unique = 3 → max = 5
  3. Window [4-10] = "cbebebe" → unique = 3 → max = 7

Output:

7


Complexity Analysis

  1. Time Complexity: O(n) → Each character enters and leaves the window once
  2. Space Complexity: O(k) → HashMap stores at most k unique characters


Edge Cases Considered

  1. k greater than number of unique characters → return -1
  2. Entire string has exactly k unique characters
  3. String with repeated characters only
  4. Minimum string length (1)


Sliding Window Pattern Importance

This problem reinforces a common sliding window + hashmap pattern used in:

  1. Longest substring problems with constraints
  2. Counting substrings with exactly K conditions
  3. Optimizing brute-force approaches to linear solutions


Conclusion

By combining sliding window with HashMap frequency tracking, we reduce an O(n²) problem to O(n).

Once you master this approach, many string and substring problems with constraints on unique characters become much easier to solve efficiently.

Related Articles

Fruit Into Baskets – Sliding Window with Two Types

Fruit Into Baskets – Sliding Window with Two Types

Learn how to maximize the number of fruits you can collect with two baskets using a sliding window and HashMap.

Read Article
Max Consecutive Ones III – Sliding Window with Limited Flips

Max Consecutive Ones III – Sliding Window with Limited Flips

Learn how to maximize consecutive 1's in a binary array by flipping at most K zeros using an optimized sliding window approach.

Read Article
Length of Longest Subarray With At Most K Frequency – Sliding Window Approach

Length of Longest Subarray With At Most K Frequency – Sliding Window Approach

Learn how to find the longest contiguous subarray where each element occurs at most K times using HashMap and sliding window.

Read Article
Longest Subarray of 1's After Deleting One Element – Sliding Window Approach

Longest Subarray of 1's After Deleting One Element – Sliding Window Approach

Learn how to maximize consecutive 1's in a binary array by deleting exactly one element using an efficient sliding window technique.

Read Article

Ai Assistant Kas