LeetCode 340: Longest Substring with At Most K Distinct Characters Solution in Python – A Step-by-Step Guide

What Is LeetCode 340: Longest Substring with At Most K Distinct Characters?

In LeetCode 340: Longest Substring with At Most K Distinct Characters, you’re given a string s and an integer k, and your task is to find the length of the longest substring that contains at most k distinct characters. For example, with s = "eceba" and k = 2, the longest substring is "ece" (length 3). This problem tests your ability to manage substring constraints efficiently, extending LeetCode 3: Longest Substring Without Repeating Characters.

Problem Statement

• Input: A string s and an integer k.
• Output: An integer—the length of the longest substring with at most k distinct characters.
• Rules:
• Substring must be contiguous.
• Count distinct characters (≤ k).
• Maximize length.

Constraints

• 1 <= s.length <= 10⁵
• 0 <= k <= 10⁵
• s contains only lowercase English letters.

Examples

• Input: s = "eceba", k = 2
• Output: 3 (Substring "ece")
• Input: s = "aa", k = 1
• Output: 2 (Substring "aa")
• Input: s = "a", k = 0
• Output: 0 (No valid substring)

Understanding the Problem: Finding the Longest Stretch

To solve LeetCode 340: Longest Substring with At Most K Distinct Characters in Python, we need to find the longest contiguous substring in s with no more than k unique characters. A naive approach—checking every substring—is O(n²), too slow for 10⁵ characters. Instead, we’ll use:

• Best Solution (Sliding Window with Hash Map): O(n) time, O(k) space—fast and scalable.
• Alternative Solution (Brute Force): O(n²) time, O(k) space—simple but inefficient.

Let’s start with the sliding window solution, explained in a beginner-friendly way.

Best Solution: Sliding Window with Hash Map

Why This Is the Best Solution

The sliding window with hash map approach is the top choice for LeetCode 340 because it’s efficient—O(n) time, O(k) space—and uses a dynamic window to track distinct characters while maximizing length. It maintains a hash map of character counts, sliding the window when the limit is exceeded. It’s like stretching a net to catch the longest haul—smart and quick!

How It Works

Think of this as a window stretcher:

• Step 1: Initialize:
• Two pointers: left (start), right (end).
• Hash map for character counts.
• Max length tracker.
• Step 2: Expand Window:
• Move right, add char to map.
• Step 3: Shrink if Needed:
• If distinct chars > k, move left, remove chars until ≤ k.
• Step 4: Update Max:
• Track longest valid window.
• Step 5: Why It Works:
• Sliding window ensures O(n) traversal.
• Hash map keeps distinct count in O(1).

It’s like fishing for the biggest catch with a limited net!

Step-by-Step Example

Example: s = "eceba", k = 2

• Init: left = 0, right = 0, map = {}, max_len = 0
• r=0: "e", map = {e:1}, len = 1, max_len = 1
• r=1: "ec", map = {e:1, c:1}, len = 2, max_len = 2
• r=2: "ece", map = {e:2, c:1}, len = 3, max_len = 3
• r=3: "eceb", map = {e:2, c:1, b:1}, distinct = 3 > 2
• Shrink: left = 1, "ceb", map = {e:1, c:1, b:1}, len = 3
• Shrink: left = 2, "eb", map = {e:1, b:1}, len = 2
• r=4: "eba", map = {e:1, b:1, a:1}, distinct = 3 > 2
• Shrink: left = 3, "ba", map = {b:1, a:1}, len = 2
• Result: max_len = 3 ("ece")

Code with Detailed Line-by-Line Explanation

Copy codeclass Solution:
    def lengthOfLongestSubstringKDistinct(self, s: str, k: int) -> int:
        if k == 0:
            return 0

        # Initialize window
        char_count = {}
        left = 0
        max_len = 0

        # Slide window
        for right in range(len(s)):
            char_count[s[right]] = char_count.get(s[right], 0) + 1

            # Shrink window if too many distinct chars
            while len(char_count) > k:
                char_count[s[left]] -= 1
                if char_count[s[left]] == 0:
                    del char_count[s[left]]
                left += 1

            # Update max length
            max_len = max(max_len, right - left + 1)

        return max_len

• Lines 3-4: Handle k=0 edge case.
• Lines 7-9: Initialize hash map, left pointer, and max length.
• Lines 12-20: Slide window:
• Add right char to map.
• Shrink if distinct > k by moving left.
• Line 22: Update max length after each valid window.
• Time Complexity: O(n)—each char processed once.
• Space Complexity: O(k)—hash map size.

This is like a window-stretching pro—fast and sleek!

Alternative Solution: Brute Force

Why an Alternative Approach?

The brute-force approach—O(n²) time, O(k) space—checks every possible substring by iterating over all start and end points, counting distinct characters. It’s the simplest way to understand the problem but too slow for 10⁵ characters, making it a baseline for learning. It’s like checking every net size—thorough but tedious!

How It Works

Check all substrings:

• Step 1: Double loop over start (i) and end (j).
• Step 2: Count distinct chars in substring i to j.
• Step 3: Update max if ≤ k distinct chars.

Step-by-Step Example

Example: s = "ece", k = 2

• i=0:
• "e": 1, max=1
• "ec": 2, max=2
• "ece": 2, max=3
• i=1:
• "c": 1, max=3
• "ce": 2, max=3
• i=2: "e": 1, max=3
• Result: 3

Code for Brute Force Approach

Copy codeclass Solution:
    def lengthOfLongestSubstringKDistinct(self, s: str, k: int) -> int:
        if k == 0:
            return 0

        max_len = 0
        for i in range(len(s)):
            char_set = set()
            for j in range(i, len(s)):
                char_set.add(s[j])
                if len(char_set) <= k:
                    max_len = max(max_len, j - i + 1)
                else:
                    break

        return max_len

• Time Complexity: O(n²)—nested loops.
• Space Complexity: O(k)—set size.

It’s a substring-checking plodder—basic but slow!

Comparing the Two Solutions

• Sliding Window with Hash Map (Best):
• Pros: O(n) time, O(k) space, fast and scalable.
• Cons: Window logic less obvious.
• Brute Force (Alternative):
• Pros: O(n²) time, O(k) space, straightforward.
• Cons: Too slow for large n.

Sliding window wins for performance.

Additional Examples and Edge Cases

• "a", 1: 1.
• "", 1: 0.
• "aabbb", 2: 5.

Both handle these, but sliding window is faster.

Complexity Breakdown

• Sliding Window: Time O(n), Space O(k).
• Brute Force: Time O(n²), Space O(k).

Sliding window is the clear choice.

Key Takeaways

• Sliding Window: Stretch smart—efficient!
• Brute Force: Check all—simple!
• Python: Dicts and loops shine—see [Python Basics](/python/basics).
• Substrings: Windows beat exhaustive search.

Final Thoughts: Stretch the String

LeetCode 340: Longest Substring with At Most K Distinct Characters in Python is a sliding window masterpiece. The hash map solution offers speed and elegance, while brute force provides a tangible baseline. Want more string challenges? Try LeetCode 3: Longest Substring Without Repeating Characters or LeetCode 159: Longest Substring with At Most Two Distinct Characters. Ready to stretch? Head to Solve LeetCode 340 on LeetCode (premium) and find that longest substring today!