Longest Substring with At Most K Distinct Characters

Description

Given a string s and a non-negative integer k, find the length of the longest substring of s that contains at most k distinct (unique) characters.

A substring is a contiguous sequence of characters within the string. For instance, "abc" is a substring of "xabcz", but "axc" is not because the characters are not consecutive in the original string.

The distinct character count of a substring is the number of unique characters appearing in it. Your goal is to find the maximum possible length among all substrings whose distinct character count does not exceed k.

If k = 0, no characters are allowed in the substring, so the answer is 0.

Examples

Example 1

Input: s = "eceba", k = 2

Output: 3

Explanation: The substring "ece" (indices 0 through 2) contains exactly 2 distinct characters: 'e' and 'c'. Its length is 3. No longer substring exists with at most 2 distinct characters — for example, "eceb" has 3 distinct characters ('e', 'c', 'b'), which exceeds k = 2. Therefore the answer is 3.

Example 2

Input: s = "aa", k = 1

Output: 2

Explanation: The entire string "aa" contains only 1 distinct character ('a'), which satisfies the constraint k = 1. Since no longer substring can exist (the whole string is already selected), the answer is 2.

Example 3

Input: s = "abcdef", k = 3

Output: 3

Explanation: Every window of 3 consecutive characters has exactly 3 distinct characters (e.g., "abc", "bcd", "cde", "def"), all satisfying k = 3. Any window of 4 characters (e.g., "abcd") contains 4 distinct characters, exceeding k. So the maximum valid length is 3.

Constraints

1 ≤ s.length ≤ 5 × 10^4
0 ≤ k ≤ 50
s consists of lowercase English letters

Editorial

Brute Force

Intuition

The most straightforward way to solve this problem is to examine every possible substring and check whether it meets our constraint.

Imagine you have a long word written on a strip of paper. You place your finger on the first letter and start sliding a second finger to the right, one letter at a time, expanding your selection. At each position you count how many different letters appear in your selected portion. As long as the count stays within k, you record the length. The moment the count exceeds k, you stop — no further expansion from this starting point can help.

You then move your first finger one position to the right, reset your counts, and repeat the entire expansion process. After trying every possible starting position, the longest valid selection you found is the answer.

To avoid recounting characters from scratch every time the right boundary extends by one, we maintain a frequency map that we update incrementally. This way, expanding by one character costs O(1) rather than O(n).

Step-by-Step Explanation

Let us trace through s = "eceba", k = 2:

Step 1: Start with i = 0. Initialize an empty frequency map. Set j = 0.

Add 'e': freq = {e:1}, distinct = 1 ≤ 2. Length = 1. max_len = 1.

Step 2: Expand j = 1.

Add 'c': freq = {e:1, c:1}, distinct = 2 ≤ 2. Length = 2. max_len = 2.

Step 3: Expand j = 2.

Add 'e': freq = {e:2, c:1}, distinct = 2 ≤ 2. Length = 3. max_len = 3.

Step 4: Expand j = 3.

Add 'b': freq = {e:2, c:1, b:1}, distinct = 3 > 2. STOP expanding from i = 0.

Step 5: Move to i = 1. Reset freq = {}. Set j = 1.

Add 'c': freq = {c:1}, distinct = 1. Length = 1.

Step 6: Expand j = 2.

Add 'e': freq = {c:1, e:1}, distinct = 2. Length = 2. (Does not beat max_len = 3.)

Step 7: Expand j = 3.

Add 'b': freq = {c:1, e:1, b:1}, distinct = 3 > 2. STOP expanding from i = 1.

Step 8: Remaining starting positions i = 2, 3, 4 yield lengths 2, 2, 1 respectively — none beat max_len = 3.

Result: max_len = 3.

Brute Force — Trying All Starting Positions — Watch how the brute force fixes each starting position and expands rightward, resetting the frequency map each time the start moves.

Algorithm

Initialize max_len = 0.
For each starting index i from 0 to n - 1:
a. Create an empty frequency map.
b. For each ending index j from i to n - 1:
- Add s[j] to the frequency map (increment its count).
- If the number of keys in the map exceeds k, break out of the inner loop.
- Otherwise, update max_len = max(max_len, j - i + 1).
Return max_len.

Code

class Solution {
public:
    int lengthOfLongestSubstringKDistinct(string s, int k) {
        int n = s.size();
        int maxLen = 0;

        for (int i = 0; i < n; i++) {
            unordered_map<char, int> freq;
            for (int j = i; j < n; j++) {
                freq[s[j]]++;
                if ((int)freq.size() > k) {
                    break;
                }
                maxLen = max(maxLen, j - i + 1);
            }
        }

        return maxLen;
    }
};

class Solution:
    def lengthOfLongestSubstringKDistinct(self, s: str, k: int) -> int:
        n = len(s)
        max_len = 0

        for i in range(n):
            freq = {}
            for j in range(i, n):
                freq[s[j]] = freq.get(s[j], 0) + 1
                if len(freq) > k:
                    break
                max_len = max(max_len, j - i + 1)

        return max_len

class Solution {
    public int lengthOfLongestSubstringKDistinct(String s, int k) {
        int n = s.length();
        int maxLen = 0;

        for (int i = 0; i < n; i++) {
            Map<Character, Integer> freq = new HashMap<>();
            for (int j = i; j < n; j++) {
                freq.merge(s.charAt(j), 1, Integer::sum);
                if (freq.size() > k) {
                    break;
                }
                maxLen = Math.max(maxLen, j - i + 1);
            }
        }

        return maxLen;
    }
}

Complexity Analysis

Time Complexity: O(n²)

The outer loop iterates over all n starting positions. For each starting position, the inner loop can extend up to the end of the string, giving O(n) work per starting position. In the worst case (e.g., when k ≥ 26 and the string uses few distinct characters), the inner loop scans almost the entire string for every start, resulting in O(n × n) = O(n²) total operations.

Space Complexity: O(min(n, k))

The frequency map stores at most k + 1 entries before we break. Since characters are drawn from a fixed alphabet of size 26, the map holds at most min(26, k + 1) entries. In terms of input size, this is O(min(n, k)).

Why This Approach Is Not Efficient

The brute force examines O(n²) substrings in the worst case. With n up to 5 × 10^4, that translates to roughly 2.5 × 10^9 operations — far too many for typical time limits of 1–2 seconds.

The root cause of the inefficiency is redundant re-examination. When the brute force finishes exploring all substrings starting at index i, it moves to i + 1 and builds the frequency map from scratch. But the substring s[i+1..j] shares almost all characters with s[i..j] — only the character at index i was removed. We are throwing away all the frequency information we just built and reconstructing it.

Key insight: If we could retain the frequency map and simply remove the leftmost character when the window becomes invalid — instead of starting over — we would avoid this redundant work. This idea leads to the sliding window technique, where both the left and right boundaries move forward and each character enters and leaves the window at most once.

Optimal Approach - Sliding Window with Hash Map

Intuition

Instead of restarting the search from every position, we maintain a flexible window over the string defined by two pointers — left and right. We expand the window by moving right forward, adding each new character to a frequency map. As long as the window has at most k distinct characters, it is valid and we record its length.

The moment the window gains a (k + 1)-th distinct character, it becomes invalid. Rather than discarding everything and starting over (as brute force does), we shrink from the left: we remove the character at left from the frequency map, advance left by one, and repeat the shrinking until the window is valid again.

Think of it like looking through a telescope with an adjustable frame. You keep widening the frame (moving right) to see more of the landscape. If you see too many colors (more than k), you slide the left edge of the frame forward until some colors disappear. The widest valid view you ever achieved is your answer.

Because both left and right only move forward — never backward — each character is added to the map at most once and removed at most once. This gives the algorithm a total of O(n) operations, a dramatic improvement over the brute force.

Step-by-Step Explanation

Let us trace through s = "eceba", k = 2:

Step 1: Initialize left = 0, max_len = 0, freq = {}.

Step 2: right = 0, char = 'e'.

Add to freq: {e:1}. Distinct = 1 ≤ 2. Valid.
Window [0, 0] = "e". max_len = max(0, 1) = 1.

Step 3: right = 1, char = 'c'.

Add to freq: {e:1, c:1}. Distinct = 2 ≤ 2. Valid.
Window [0, 1] = "ec". max_len = max(1, 2) = 2.

Step 4: right = 2, char = 'e'.

Add to freq: {e:2, c:1}. Distinct = 2 ≤ 2. Valid (no new character).
Window [0, 2] = "ece". max_len = max(2, 3) = 3.

Step 5: right = 3, char = 'b'.

Add to freq: {e:2, c:1, b:1}. Distinct = 3 > 2. Invalid!

Step 6: Shrink — remove s[left=0] = 'e'.

freq: {e:1, c:1, b:1}. Distinct still 3. left becomes 1.

Step 7: Shrink again — remove s[left=1] = 'c'.

freq of 'c' drops to 0, delete it: {e:1, b:1}. Distinct = 2 ≤ 2. Valid!
left becomes 2. Window [2, 3] = "eb". Length = 2, does not beat max_len = 3.

Step 8: right = 4, char = 'a'.

Add to freq: {e:1, b:1, a:1}. Distinct = 3 > 2. Invalid!

Step 9: Shrink — remove s[left=2] = 'e'.

freq of 'e' drops to 0, delete it: {b:1, a:1}. Distinct = 2 ≤ 2. Valid!
left becomes 3. Window [3, 4] = "ba". Length = 2, does not beat max_len = 3.

Step 10: All characters processed. Return max_len = 3.

Sliding Window — Expand Right, Shrink Left — Watch the window expand by advancing the right pointer and shrink by advancing the left pointer whenever distinct characters exceed k. Both pointers only move forward.

Algorithm

Initialize left = 0, max_len = 0, and an empty frequency map freq.
Iterate right from 0 to n - 1:
a. Add s[right] to freq (increment its count).
b. While freq has more than k keys (distinct characters):
- Decrement the count of s[left] in freq.
- If the count reaches 0, remove that key entirely.
- Increment left.
  c. Update max_len = max(max_len, right - left + 1).
Return max_len.

Code

class Solution {
public:
    int lengthOfLongestSubstringKDistinct(string s, int k) {
        int n = s.size();
        int maxLen = 0;
        int left = 0;
        unordered_map<char, int> freq;

        for (int right = 0; right < n; right++) {
            freq[s[right]]++;

            // Shrink window until at most k distinct characters remain
            while ((int)freq.size() > k) {
                freq[s[left]]--;
                if (freq[s[left]] == 0) {
                    freq.erase(s[left]);
                }
                left++;
            }

            maxLen = max(maxLen, right - left + 1);
        }

        return maxLen;
    }
};

class Solution:
    def lengthOfLongestSubstringKDistinct(self, s: str, k: int) -> int:
        n = len(s)
        max_len = 0
        left = 0
        freq = {}

        for right in range(n):
            freq[s[right]] = freq.get(s[right], 0) + 1

            # Shrink window until at most k distinct characters remain
            while len(freq) > k:
                freq[s[left]] -= 1
                if freq[s[left]] == 0:
                    del freq[s[left]]
                left += 1

            max_len = max(max_len, right - left + 1)

        return max_len

class Solution {
    public int lengthOfLongestSubstringKDistinct(String s, int k) {
        int n = s.length();
        int maxLen = 0;
        int left = 0;
        Map<Character, Integer> freq = new HashMap<>();

        for (int right = 0; right < n; right++) {
            freq.merge(s.charAt(right), 1, Integer::sum);

            // Shrink window until at most k distinct characters remain
            while (freq.size() > k) {
                char leftChar = s.charAt(left);
                freq.merge(leftChar, -1, Integer::sum);
                if (freq.get(leftChar) == 0) {
                    freq.remove(leftChar);
                }
                left++;
            }

            maxLen = Math.max(maxLen, right - left + 1);
        }

        return maxLen;
    }
}

Complexity Analysis

Time Complexity: O(n)

The right pointer traverses the string once from index 0 to n − 1, contributing O(n) increments. The left pointer also only moves forward and can advance at most n times in total across all iterations. Each character is added to the frequency map exactly once (when right reaches it) and removed at most once (when left passes it). All map operations (insert, delete, lookup) are O(1) amortized with a hash map. Therefore, the total work is O(n) + O(n) = O(n).

Space Complexity: O(k)

The frequency map stores at most k + 1 entries at any point — the moment it reaches k + 1, the while loop immediately removes entries until the count drops back to k. Since k ≤ 50, this is effectively O(1) for this problem's constraints. More generally, it is O(min(n, k, |Σ|)) where |Σ| is the alphabet size (26 for lowercase English).