Longest Substring with K Uniques

JavaView on GFG

Time: O(n)

Space: O(k)

Intuition

Find longest substring with exactly k unique characters. Sliding window.

Algorithm

1Sliding window with frequency map. Expand right. When distinct > k: shrink left. Track max when distinct == k.

Common Pitfalls

•Same as LC 395 variant. Exactly k: use at-most-k minus at-most-(k-1). Or direct sliding window.

Longest Substring with K Uniques.java

Java

// Approach: Sliding window. Maintain frequency map; shrink left when unique count > k.
// Time: O(n) Space: O(k)
import java.util.*;

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

        for (int i = 0; i < s.length(); i++) {
            char ch = s.charAt(i);

            map.put(ch, map.getOrDefault(ch, 0) + 1);

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

                left++;
            }

            if (map.size() == k)
                maxLen = Math.max(maxLen, i - left + 1);
        }

        return maxLen;
    }
}

Was this solution helpful?