Problem Description

Given a string s and an integer k, you are asked to find the length of the longest substring of s that contains at most k distinct characters.

In other words, you want the length of the longest continuous segment of s where there are no more than k different characters present.

• Input: A string s and an integer k
• Output: An integer representing the length of the longest such substring

Constraints:

• 0 ≤ k ≤ 26
• 1 ≤ |s| ≤ 105
• s consists of English letters

Thought Process

At first glance, it might seem natural to consider all possible substrings and count the number of distinct characters in each. However, this brute-force approach would be extremely slow, especially for long strings.

Instead, we look for a way to efficiently "slide" through the string, keeping track of the characters within a current window, and expanding or shrinking this window as needed. This leads us to the sliding window technique.

The key insight is: As we move through the string, we can efficiently maintain a count of characters within the current window and adjust the window's size to always satisfy the "at most k distinct characters" constraint.

Solution Approach

We use the sliding window algorithm with two pointers (left and right) and a hash map (or dictionary) to track the count of each character within the window.

1. Initialize: Set two pointers, left and right, both at the start of the string. Create a hash map to count occurrences of each character in the current window. Set max_len to 0.
2. Expand the window: Move right forward one character at a time, adding the character to the hash map and updating its count.
3. Check constraint: If the number of distinct characters in the hash map exceeds k, shrink the window from the left by moving left forward and updating the hash map accordingly (decrement the count, remove the character if its count reaches 0).
4. Update answer: After each expansion (and as long as the window is valid), update max_len to be the maximum of its current value and the window size (right - left + 1).
5. Continue until right reaches the end of the string.

We use a hash map because it allows us to quickly check how many distinct characters are in the current window (the size of the map), and to efficiently update character counts as the window moves.

Example Walkthrough

Example: s = "eceba", k = 2

1. Start with left = 0, right = 0, window = "e", map = {e:1}, distinct = 1 (valid), max_len = 1
2. Move right to 1: window = "ec", map = {e:1, c:1}, distinct = 2 (valid), max_len = 2
3. Move right to 2: window = "ece", map = {e:2, c:1}, distinct = 2 (valid), max_len = 3
4. Move right to 3: window = "eceb", map = {e:2, c:1, b:1}, distinct = 3 (not valid)
   • Shrink window from left: remove 'e' at index 0, map = {e:1, c:1, b:1}
   • Still 3 distinct, move left to 1, remove 'c', map = {e:1, c:0, b:1} → remove c (count 0), map = {e:1, b:1}
   • Now 2 distinct, window is "eb", left = 2, right = 3
   max_len remains 3
5. Move right to 4: window = "eba", map = {e:1, b:1, a:1}, distinct = 3 (not valid)
   • Shrink window from left: remove 'e', map = {e:0, b:1, a:1} → remove e, map = {b:1, a:1}
   • Now 2 distinct, window is "ba", left = 3, right = 4
   max_len remains 3

The longest substring with at most 2 distinct characters is "ece" with length 3.

Time and Space Complexity

Brute-force approach: For every possible substring, count the number of distinct characters. This takes O(N²) substrings, and for each, O(N) to count distinct characters, so total O(N³).

Optimized (Sliding Window) approach:

• Time Complexity: O(N), where N is the length of the string. Each character is added and removed from the hash map at most once as the window slides.
• Space Complexity: O(K), since the hash map stores at most K keys (distinct characters in the window).

Summary

This problem is a classic example of using the sliding window technique to efficiently handle substring constraints. By tracking character counts in a hash map and dynamically adjusting the window, we can solve the problem in linear time. The approach is both elegant and practical for large inputs, making it a staple technique for substring and subarray problems with constraints.

Code Implementation

from collections import defaultdict

class Solution:
    def lengthOfLongestSubstringKDistinct(self, s: str, k: int) -> int:
        if k == 0 or not s:
            return 0
        left = 0
        max_len = 0
        char_map = defaultdict(int)
        for right, char in enumerate(s):
            char_map[char] += 1
            while len(char_map) > k:
                char_map[s[left]] -= 1
                if char_map[s[left]] == 0:
                    del char_map[s[left]]
                left += 1
            max_len = max(max_len, right - left + 1)
        return max_len
      

#include <unordered_map>
#include <string>
using namespace std;

class Solution {
public:
    int lengthOfLongestSubstringKDistinct(string s, int k) {
        if (k == 0 || s.empty()) return 0;
        unordered_map<char, int> char_map;
        int left = 0, max_len = 0;
        for (int right = 0; right < s.size(); ++right) {
            char_map[s[right]]++;
            while (char_map.size() > k) {
                char_map[s[left]]--;
                if (char_map[s[left]] == 0) {
                    char_map.erase(s[left]);
                }
                left++;
            }
            max_len = max(max_len, right - left + 1);
        }
        return max_len;
    }
};
      

import java.util.HashMap;

class Solution {
    public int lengthOfLongestSubstringKDistinct(String s, int k) {
        if (k == 0 || s.length() == 0) return 0;
        HashMap<Character, Integer> map = new HashMap<>();
        int left = 0, maxLen = 0;
        for (int right = 0; right < s.length(); right++) {
            char c = s.charAt(right);
            map.put(c, map.getOrDefault(c, 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++;
            }
            maxLen = Math.max(maxLen, right - left + 1);
        }
        return maxLen;
    }
}
      

function lengthOfLongestSubstringKDistinct(s, k) {
    if (k === 0 || s.length === 0) return 0;
    const map = new Map();
    let left = 0, maxLen = 0;
    for (let right = 0; right < s.length; right++) {
        map.set(s[right], (map.get(s[right]) || 0) + 1);
        while (map.size > k) {
            map.set(s[left], map.get(s[left]) - 1);
            if (map.get(s[left]) === 0) {
                map.delete(s[left]);
            }
            left++;
        }
        maxLen = Math.max(maxLen, right - left + 1);
    }
    return maxLen;
}