NUHMAN.com

Introduction

LeetCode 340 is a classic sliding window problem that requires you to find the longest substring in a string that contains at most k distinct characters. This problem elegantly combines hash maps and two-pointer techniques to solve substring problems in linear time.

Problem Statement

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

Example

python

Input: s = "eceba", k = 2  
Output: 3  
Explanation: The substring is "ece" with 2 distinct characters.

🔍 Observations

• The substring must be continuous.
• The order matters.
• You need to track the distinct characters and shrink the window when they exceed k.

✅ Python Solution Using Sliding Window

We'll use:

• A left pointer (left) to mark the beginning of the window.
• A hashmap (char_map) to store the frequency of characters in the current window.
• Expand the window to the right while the number of distinct characters is ≤ k.
• Shrink the window from the left when it exceeds k.

python

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 in range(len(s)):
            char_map[s[right]] += 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

🧠 Step-by-Step Walkthrough

Let’s take s = "eceba" and k = 2:

1. right = 0, char = 'e', map = {'e':1}
2. right = 1, char = 'c', map = {'e':1, 'c':1} → valid (2 ≤ 2)
3. right = 2, char = 'e', map = {'e':2, 'c':1} → valid

• Max len = 3 ("ece")

1. right = 3, char = 'b', map = {'e':2, 'c':1, 'b':1} → 3 > 2

• Shrink: left = 1, map = {'e':1, 'c':1, 'b':1}
• Shrink: left = 2, map = {'e':1, 'b':1} → valid

1. right = 4, char = 'a', map = {'e':1, 'b':1, 'a':1} → shrink again

Eventually, the longest substring with ≤ 2 distinct characters is "ece", length = 3.

⏱️ Complexity Analysis

MetricValueTime ComplexityO(n)Space ComplexityO(k)

• Each character is added and removed from the hash map at most once.
• Efficient even for large strings.

💡 Edge Cases

InputOutputs = "", k = 20s = "a", k = 00s = "a", k = 11

✅ Conclusion

LeetCode 340: Longest Substring with At Most K Distinct Characters is an essential sliding window problem that strengthens your grasp on managing dynamic windows with constraints. It's efficient and widely applicable in string parsing, logs analysis, and streaming data.

This is a must-know pattern for coding interviews and real-world scenarios!