求「找到包含K个唯一字符的最长子串」算法的时间复杂度

Hey there! Let's dive into solving the "longest substring with K unique characters" problem—this is a classic sliding window problem, so it's perfect to break down with your example string "aabbccdd" to make things clear.

First, let's confirm the expected results with your example:

• When K=1, the longest valid substring is "aa" (or "bb", "cc", "dd"—all have length 2)
• When K=2, we get "aabb" (or "bbcc", "ccdd"—length 4)
• When K=3, the longest is "aabbcc" (or "bbccdd"—length 6)

How the Sliding Window Approach Works #

The sliding window method uses two pointers (start and end) to represent the current substring we're examining, plus a dictionary to track character frequencies inside the window. Here's the step-by-step breakdown:

1. Initialize variables: Set start = 0, max_length = 0, and an empty char_count dictionary to keep track of how many times each character appears in the current window.
2. Expand the window with the end pointer:
   • For each character at position end, add it to char_count (increment its count if it's already there, or set it to 1 if it's new).
3. Shrink the window if needed:
   • If the number of unique characters in char_count exceeds K, we need to shrink the window from the left:
     • Decrement the count of the character at start in char_count.
     • If that count drops to 0, remove the character from the dictionary (since it's no longer present in the window).
     • Move the start pointer right by one.
   • Repeat this until the window has ≤ K unique characters.
4. Update the maximum length:
   • Calculate the current window length (end - start + 1). If this is larger than max_length, update max_length to this value.
   • Note: If the problem asks for exactly K unique characters (not at most), add a check here—only update max_length when len(char_count) == K.

Example Python Code #

Here's a concrete implementation that matches your example:

def longest_substring_with_k_unique(s, k):
    if k == 0 or not s:
        return 0
    
    char_count = {}
    start = 0
    max_len = 0
    
    for end in range(len(s)):
        current_char = s[end]
        char_count[current_char] = char_count.get(current_char, 0) + 1
        
        # Shrink window until we have <= K unique characters
        while len(char_count) > k:
            left_char = s[start]
            char_count[left_char] -= 1
            if char_count[left_char] == 0:
                del char_count[left_char]
            start += 1
        
        # Uncomment the line below if you need EXACTLY K unique chars
        # if len(char_count) == k:
        current_window_length = end - start + 1
        if current_window_length > max_len:
            max_len = current_window_length
    
    return max_len

# Test with your sample string
sample_str = "aabbccdd"
print(longest_substring_with_k_unique(sample_str, 1))  # Output: 2
print(longest_substring_with_k_unique(sample_str, 2))  # Output: 4
print(longest_substring_with_k_unique(sample_str, 3))  # Output: 6

Key Takeaways #

• Time Complexity: O(n), where n is the length of the string. Each character is processed twice (once by end, once by start), so it's linear time.
• Space Complexity: O(K), since the dictionary will hold at most K+1 unique characters at any point.
• Edge Cases: Make sure to handle empty strings, K=0, or when K is larger than the total number of unique characters in the string (in that case, the entire string is the answer).

内容的提问来源于stack exchange，提问作者asndonsadoasndo231213