Course4all
Join us on telegram
Home/dsa/Sliding Window/Longest Substring with At Most K Distinct Characters

Longest Substring with At Most K Distinct Characters

Master this topic with zero to advance depth.

Longest Substring with At Most K Distinct Characters

Given a string s and an integer k, return the length of the longest substring that contains at most k distinct characters.

Visual Representation

s = "eceba", k = 2 [e] [e, c] [e, c, e] (Distinct: 2 <= 2, Valid!) [e, c, e, b] (Distinct: 3 > 2, INVALID!)
Medium

Examples

Input: s = "eceba", k = 2
Output: 3
Approach 1

Level I: Brute Force

Intuition

Check every possible substring and count unique characters. Update maximum length if the count is ≤k\le k.

⏱ O(N^2)💾 O(K)
java
public class Solution {
    public int lengthOfLongestSubstringKDistinct(String s, int k) {
        int maxLen = 0;
        for (int i = 0; i < s.length(); i++) {
            Set<Character> distinct = new HashSet<>();
            for (int j = i; j < s.length(); j++) {
                distinct.add(s.charAt(j));
                if (distinct.size() <= k) maxLen = Math.max(maxLen, j - i + 1);
                else break;
            }
        }
        return maxLen;
    }
}
Approach 2

Level III: Optimal (Sliding Window)

Intuition

Thought Process

Standard variable-size sliding window. Maintain a frequency map of characters in the window. When map size exceeds k, shrink from the left.

Pattern: Variable Size Sliding Window (K Distinct)

⏱ O(N)💾 O(K)
java
public class Solution {
    public int lengthOfLongestSubstringKDistinct(String s, int k) {
        Map<Character, Integer> counts = new HashMap<>();
        int left = 0, maxLen = 0;
        for (int right = 0; right < s.length(); right++) {
            char c = s.charAt(right);
            counts.put(c, counts.getOrDefault(c, 0) + 1);
            while (counts.size() > k) {
                char out = s.charAt(left++);
                counts.put(out, counts.get(out) - 1);
                if (counts.get(out) == 0) counts.remove(out);
            }
            maxLen = Math.max(maxLen, right - left + 1);
        }
        return maxLen;
    }
}
← Previous QuestionFrequency of the Most Frequent Element
Next Question →Count Complete Subarrays in an Array