Course4all
Join us on telegram
Home/dsa/Two Pointers/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 of s that contains at most k distinct characters.

Visual Representation

s = "eceba", k = 2 Indices: 0 1 2 3 4 Chars: e c e b a 1. Window [0,0]: {e} (1 distinct) <= 2, Max=1 2. Window [0,1]: {e, c} (2 distinct) <= 2, Max=2 3. Window [0,2]: {e, c, e} (2 distinct) <= 2, Max=3 4. Window [0,3]: {e, c, e, b} (3 distinct) > 2 - Shrink from left: [1,3] -> {c, e, b} (3 distinct) > 2 - Shrink from left: [2,3] -> {e, b} (2 distinct) <= 2, Max=3
Hard

Examples

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

The substring is "ece" which has length 3.

Approach 1

Level I: Brute Force

Intuition

Generate all possible substrings and for each substring, count the number of distinct characters. If it's <= k, update the maximum length.

⏱ O(N^2)💾 O(K)

Detailed Dry Run

Input: s = "eceba", k = 2

  1. i=0:
    • j=0 (e): {e}, size=1 <= 2. maxLen = 1
    • j=1 (c): {e, c}, size=2 <= 2. maxLen = 2
    • j=2 (e): {e, c}, size=2 <= 2. maxLen = 3
    • j=3 (b): {e, c, b}, size=3 > 2. BREAK
  2. i=1:
    • j=1 (c): {c}, size=1 <= 2. maxLen = 3
    • j=2 (e): {c, e}, size=2 <= 2. maxLen = 3
    • j=3 (b): {c, e, b}, size=3 > 2. BREAK
java
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;
}

⚠️ Common Pitfalls & Tips

O(N^2) time complexity is too slow for N=10^5.

Approach 2

Level II: Sliding Window (Using Dictionary/Frequency Map)

Intuition

Instead of checking all substrings, use two pointers to maintain a window. Expand the right pointer, and if the count of unique characters exceeds k, move the left pointer until the count is back to k.

⏱ O(N)💾 O(K)

Detailed Dry Run

Input: s = "eceba", k = 2

  1. r=0 (e): map={e:1}, size=1. max=1
  2. r=1 (c): map={e:1, c:1}, size=2. max=2
  3. r=2 (e): map={e:2, c:1}, size=2. max=3
  4. r=3 (b): map={e:2, c:1, b:1}, size=3 > 2.
    • Move l=0 (e): map={e:1, c:1, b:1}, size=3
    • Move l=1 (c): map={e:1, b:1}, size=2. loop ends.
java
public int lengthOfLongestSubstringKDistinct(String s, int k) {
    if (s.length() == 0 || k == 0) return 0;
    Map<Character, Integer> counts = new HashMap<>();
    int left = 0, maxLen = 0;
    for (int right = 0; right < s.length(); right++) {
        counts.put(s.charAt(right), counts.getOrDefault(s.charAt(right), 0) + 1);
        while (counts.size() > k) {
            char leftChar = s.charAt(left);
            counts.put(leftChar, counts.get(leftChar) - 1);
            if (counts.get(leftChar) == 0) counts.remove(leftChar);
            left++;
        }
        maxLen = Math.max(maxLen, right - left + 1);
    }
    return maxLen;
}

⚠️ Common Pitfalls & Tips

O(N) time but O(K) space for the mapping.

Approach 3

Level III: Optimal (Sliding Window + Hash Map)

Intuition

Use a sliding window with two pointers i and j. Maintain a frequency map of characters in the current window. If the number of distinct characters exceeds k, shrink the window from the left until it's valid again.

Add characters from the right. When map.size() > k, remove from the left and update the count. Keep track of the max j - i + 1.

⏱ O(N)💾 O(k)

Detailed Dry Run

eceba, k=2. Window: [e,c,e] -> ok, max=3. Add 'b': [e,c,e,b] -> distinct=3 > 2. Shrink left until distinct <= 2: [e,b] -> ok, len=2.

java
public int lengthOfLongestSubstringKDistinct(String s, int k) {
    Map<Character, Integer> counts = new HashMap<>();
    int i = 0, j = 0, maxLen = 0;
    for (j = 0; j < s.length(); j++) {
        counts.put(s.charAt(j), counts.getOrDefault(s.charAt(j), 0) + 1);
        while (counts.size() > k) {
            char leftChar = s.charAt(i);
            counts.put(leftChar, counts.get(leftChar) - 1);
            if (counts.get(leftChar) == 0) counts.remove(leftChar);
            i++;
        }
        maxLen = Math.max(maxLen, j - i + 1);
    }
    return maxLen;
}

⚠️ Common Pitfalls & Tips

Ensure the character count reaches zero before removing it from the map. Using a map size as the distinct count is robust.

← Previous QuestionMinimum Window Subsequence
Next Question →Subarrays with K Different Integers