Longest Substring With At Most K Distinct Characters | Two Pointers and Sliding Window

This chapter explores the algorithmic mechanics behind finding the Longest Substring With At Most K Distinct Characters. Building upon foundational sliding window patterns, this guide examines three distinct approaches—from a naive brute-force method to an optimal linear-time solution that eliminates redundant inner loop traversals.

1. Problem Statement and Definition

Given a string s and an integer k, the objective is to find the length of the longest contiguous substring that contains at most k distinct characters.

• Substring Definition: Any consecutive portion of a string.
• Valid Condition: The number of unique characters in the selected substring $\le k$.
• Target Metric: Maximum length among all valid substrings.

Concrete Example Walkthrough

Consider string s = "aaabbccd" and k = 2:

• Substring "aaabb": Length is $5$, distinct characters are {a, b} ($2 \le 2$). This is valid.
• Substring "aaabbc": Length is $6$, distinct characters are {a, b, c} ($3 > 2$). This is invalid.

2. Real-Life Analogy: The Sliding Window Ticket Booth

Analogy: Imagine running an exclusive theater box office where visitors enter continuously from the right side. The venue has a strict fire-safety limit: at most $k$ different ticket types can be inside the lobby at any given moment.

As long as the variety of guests remains within limit $k$, you keep welcoming new people and celebrating a larger crowd size. The moment a $(k+1)$-th distinct ticket type enters, the lobby becomes illegal. To restore order, you must escort guests out from the front of the line until variety drops back to safety.

3. Approach 1: The Naive Brute Force Solution

The most intuitive way to solve this problem is to generate every possible substring, count its distinct characters using a hash map, and verify whether its size is $\le k$.

Brute Force Mechanics

1. Iterate over every possible starting index i from 0 to n-1.
2. Clear the hash map for each new starting position.
3. Expand rightwards with index j, adding characters and their frequencies to the hash map.
4. If the map size exceeds k, stop expanding further from this starting point.
5. If valid, update the max_length = max(max_length, j - i + 1).

Brute Force Pseudo-Code

def longestSubstringKDistinct(s: str, k: int) -> int:
    max_length = 0
    n = len(s)
    
    for i in range(n):
        freq_map = {}
        for j in range(i, n):
            freq_map[s[j]] = freq_map.get(s[j], 0) + 1
            
            # Check validity
            if len(freq_map) <= k:
                max_length = max(max_length, j - i + 1)
            else:
                # Exceeded distinct character limit, break inner loop
                break
                
    return max_length

Complexity Analysis

• Time Complexity: $O(N^2 \cdot \text{Map Operations})$, where map lookup/insertion takes $O(1)$ (with unordered maps) or $O(\log \text{charset})$ (up to $O(\log 256)$).
• Space Complexity: $O(\text{charset})$ to store character frequencies in the map (at most $256$ for extended ASCII).

4. Approach 2: Standard Sliding Window ($O(2N)$)

To optimize beyond $O(N^2)$, we introduce the Two-Pointer / Sliding Window technique using a left pointer (L) and a right pointer (R), both initialized to 0.

Execution Flow Walkthrough

1. Expand the window by moving R to the right, inserting s[R] into a frequency map.
2. If the map size exceeds k, the window becomes invalid.
3. Shrink the window from the left by incrementing L and decrementing the frequency of s[L].
4. If a character's frequency drops to 0, completely remove it from the map.
5. Update max_length whenever the window is valid.

Standard Sliding Window Pseudo-Code

def longestSubstringKDistinct(s: str, k: int) -> int:
    max_length = 0
    l = 0
    freq_map = {}
    
    for r in range(len(s)):
        # 1. Expand window
        freq_map[s[r]] = freq_map.get(s[r], 0) + 1
        
        # 2. Shrink window while invalid
        while len(freq_map) > k:
            freq_map[s[l]] -= 1
            if freq_map[s[l]] == 0:
                del freq_map[s[l]]
            l += 1
            
        # 3. Update max length when valid
        if len(freq_map) <= k:
            max_length = max(max_length, r - l + 1)
            
    return max_length

5. Approach 3: Optimized Sliding Window ($O(N)$)

While Approach 2 runs in $O(2N)$ time due to the inner while loop potentially shrinking multiple times per outer step, we can optimize this further.

The Core Insight

When our window size reaches a maximum valid length (say, length 5), we never actually need our window to shrink below that maximum size again. If we encounter an invalid state, instead of aggressively shrinking L until the map size drops back below k, we only need to shrink the window by at most one element (or enough to maintain our best historical window size).

Optimized Sliding Window Algorithm

• When len(freq_map) > k, rather than running a while loop that strips multiple characters, replace it with a simple if statement.
• Increment l by 1 when invalid, decrementing the frequency of s[l] and removing it if its count hits 0.
• This ensures our window size never shrinks, locking in our best window size and only expanding when a longer valid window is discovered.

Optimized Implementation Pseudo-Code

def longestSubstringKDistinctOptimized(s: str, k: int) -> int:
    max_length = 0
    l = 0
    freq_map = {}
    
    for r in range(len(s)):
        # Expand window
        freq_map[s[r]] = freq_map.get(s[r], 0) + 1
        
        # Optimized check: shrink by at most 1 element if invalid
        if len(freq_map) > k:
            freq_map[s[l]] -= 1
            if freq_map[s[l]] == 0:
                del freq_map[s[l]]
            l += 1
            
        # Update max length if valid
        if len(freq_map) <= k:
            max_length = max(max_length, r - l + 1)
            
    return max_length

6. Comprehensive Complexity Synthesis

7. Summary and Key Takeaways

• Problem Classification: Substring optimization problems with constraint checks map naturally to the Two-Pointer / Sliding Window paradigm.
• Frequency Tracking: Hash maps or frequency arrays are essential for tracking distinct character counts in $O(1)$ time.
• Window Invariant: A valid window maintains $\le k$ distinct characters at all times.
• Shrinking Mechanics: In standard sliding windows, use a while loop to prune invalid elements; in optimized variants, shifting L conditionally avoids redundant shrink operations.
• Space Efficiency: Space complexity is bounded by the character set size (e.g., $256$ for ASCII or $26$ for lowercase English alphabets), treating space complexity as $O(1)$ relative to input string length $N$.