LeetCode 159: Longest Substring with At Most Two Distinct Characters Solution in Python Explained

Problem Statement

In LeetCode 159, you’re given a string s. Your task is to find the length of the longest substring that contains at most two distinct characters. This differs from file reading like LeetCode 158: Read N Characters Given Read4 II, focusing on substring analysis rather than buffered reading.

Constraints

• 1 <= s.length <= 10^5
• s consists of English letters, digits, and symbols

Example

Let’s see some cases:

Copy codeInput: s = "eceba"
Output: 3
Explanation: "ece" is the longest substring with at most 2 distinct characters ('e', 'c').

Copy codeInput: s = "ccaabbb"
Output: 5
Explanation: "aabbb" has 2 distinct characters ('a', 'b').

Copy codeInput: s = "a"
Output: 1
Explanation: Single character, length 1.

These examples show we’re seeking the longest valid substring.

Understanding the Problem

How do you solve LeetCode 159: Longest Substring with At Most Two Distinct Characters in Python? Take s = "eceba". We need the longest substring with at most two distinct characters—"ece" (length 3) fits with 'e' and 'c', while "eceba" has three ('e', 'c', 'b'). For "ccaabbb", "aabbb" (length 5) works with 'a' and 'b'. This isn’t a stack problem like LeetCode 155: Min Stack; it’s about substring optimization. We’ll use: 1. Sliding Window with Hash Map: O(n) time, O(1) space—our best solution. 2. Brute Force with Substring Check: O(n³) time, O(1) space—an alternative.

Let’s dive into the best solution.

Best Solution: Sliding Window with Hash Map Approach

Explanation

Sliding Window with Hash Map uses a sliding window to track substrings with at most two distinct characters:

• Maintain a hash map of character counts.
• Expand the window right, adding characters.
• If distinct characters exceed 2, shrink from the left until valid.
• Track the maximum length.

This is the best solution due to its O(n) time complexity (single pass), O(1) space (hash map size ≤ 3), and efficient window management, making it optimal and scalable.

For "eceba":

• Window "e" → 1 char.
• "ec" → 2 chars.
• "ece" → 2 chars, max=3.
• "eceb" → 3 chars, shrink to "ceb", then "eba", max=3.

Step-by-Step Example

Example 1: s = "eceba"

Goal: Return 3.

• Start: count = {{, left = 0, max_len = 0.
• Step 1: i=0, 'e'.
• count = {'e':1{, 1 char, max_len = 1.
• Step 2: i=1, 'c'.
• count = {'e':1,'c':1{, 2 chars, max_len = 2.
• Step 3: i=2, 'e'.
• count = {'e':2,'c':1{, 2 chars, max_len = 3.
• Step 4: i=3, 'b'.
• count = {'e':2,'c':1,'b':1{, 3 chars.
• Shrink: left = 0, remove 'e', count = {'e':1,'c':1,'b':1{, still 3.
• left = 1, remove 'c', count = {'e':1,'b':1{, 2 chars, max_len = 3.
• Step 5: i=4, 'a'.
• count = {'e':1,'b':1,'a':1{, 3 chars.
• left = 2, remove 'e', count = {'b':1,'a':1{, max_len = 3.
• Finish: Return 3.

Example 2: s = "ccaabbb"

Goal: Return 5.

• Start: count = {{, left = 0, max_len = 0.
• Step 1-2: "cc", count = {'c':2{, max_len = 2.
• Step 3: "cca", count = {'c':2,'a':1{, max_len = 3.
• Step 4-5: "ccaa", "ccaab", count = {'c':2,'a':2,'b':1{, shrink to "aabbb".
• Step 6-7: "aabbb", count = {'a':2,'b':3{, max_len = 5.
• Finish: Return 5.

Example 3: s = "a"

Goal: Return 1.

• Step 1: count = {'a':1{, max_len = 1.
• Finish: Return 1.

How the Code Works (Sliding Window with Hash Map) – Detailed Line-by-Line Explanation

Here’s the Python code with a thorough breakdown:

Copy codedef lengthOfLongestSubstringTwoDistinct(s: str) -> int:
    # Line 1: Handle base cases
    if len(s) <= 2:
        # If string is short (e.g., "a"), return length
        return len(s)

    # Line 2: Initialize variables
    count = {{
    # Char count map (e.g., {{)
    left = 0
    # Left window boundary (e.g., 0)
    max_len = 0
    # Max length found (e.g., 0)

    # Line 3: Slide window over string
    for right in range(len(s)):
        # right = right window boundary (e.g., 0 to 4)

        # Line 4: Add right character
        count[s[right]] = count.get(s[right], 0) + 1
        # Update count (e.g., {'e':1{, then {'e':1,'c':1{)

        # Line 5: Shrink window if too many distinct chars
        while len(count) > 2:
            # If > 2 chars (e.g., {'e':2,'c':1,'b':1{)
            count[s[left]] -= 1
            # Decrease left char count (e.g., 'e':1)
            if count[s[left]] == 0:
                # If count becomes 0 (e.g., 'c':0)
                del count[s[left]]
                # Remove char (e.g., {'e':1,'b':1{)
            left += 1
            # Move left (e.g., 1)

        # Line 6: Update max length
        max_len = max(max_len, right - left + 1)
        # e.g., max(0, 2-0+1)=3

    # Line 7: Return maximum length
    return max_len
    # e.g., 3 for "eceba"

This detailed breakdown clarifies how the sliding window with a hash map efficiently finds the longest substring.

Alternative: Brute Force with Substring Check Approach

Explanation

Brute Force with Substring Check generates all possible substrings and checks each for at most two distinct characters:

• For each start index, extend to all end indices.
• Count distinct characters in each substring.
• Track the maximum valid length.

It’s a practical alternative, simple but O(n³) time (O(n²) substrings, O(n) check), using O(1) space beyond temporary sets.

For "eceba":

• "e" → 1, "ec" → 2, "ece" → 2, "eceb" → 3, "eceba" → 3, etc.
• Max valid = 3 ("ece").

Step-by-Step Example (Alternative)

For "eceba":

• Step 1: i=0: "e"=1, "ec"=2, "ece"=2, "eceb"=3, "eceba"=3, max=3.
• Step 2: i=1: "c"=1, "ce"=2, "ceb"=3, "ceba"=4, max=3.
• Step 3: i=2: "e"=1, "eb"=2, "eba"=3, max=3.
• Finish: Return 3.

How the Code Works (Brute Force)

Copy codedef lengthOfLongestSubstringTwoDistinctBrute(s: str) -> int:
    max_len = 0
    for i in range(len(s)):
        for j in range(i, len(s)):
            substring = s[i:j+1]
            if len(set(substring)) <= 2:
                max_len = max(max_len, j - i + 1)
    return max_len

Complexity

• Sliding Window with Hash Map:
• Time: O(n) – single pass.
• Space: O(1) – hash map size ≤ 3.
• Brute Force with Substring Check:
• Time: O(n³) – all substrings with check.
• Space: O(1) – constant space (set aside).

Efficiency Notes

Sliding Window with Hash Map is the best solution with O(n) time and O(1) space, offering optimal efficiency—Brute Force with Substring Check uses O(n³) time, making it simpler but far slower, though space-efficient.

Key Insights

• Sliding Window: Efficient tracking.
• Hash Map: Counts distinct chars.
• Brute: Exhaustive but slow.

Additional Example

For s = "aaa":

• Goal: 3.
• Sliding: "aaa" has 1 char, length=3.

Edge Cases

• Single Char: "a" → 1.
• Two Chars: "ab" → 2.
• All Same: "aaa" → 3.

Both solutions handle these well.

Final Thoughts

LeetCode 159: Longest Substring with At Most Two Distinct Characters in Python is a rewarding substring challenge. The Sliding Window with Hash Map solution excels with its efficiency and clarity, while Brute Force with Substring Check offers a straightforward approach. Want more? Try LeetCode 3: Longest Substring Without Repeating Characters for a related challenge or LeetCode 94: Binary Tree Inorder Traversal for tree skills. Ready to practice? Solve LeetCode 159 on LeetCode with "eceba", aiming for 3—test your skills now!