Longest Substring with At Most K Distinct Characters

▶

Steps

setup

Initialize pointers and data structures

Set left pointer and max_length to 0. Initialize an empty ordered dictionary to track characters and their last seen indices.

💡 Starting with empty window and no characters tracked sets the stage for the sliding window to grow.

Line:

left = 0
max_length = 0
last_seen = OrderedDict()

💡 The algorithm prepares to scan the string with a flexible window and track character positions efficiently.

expand

Expand window to include 'e' at index 0

Move right pointer to 0 and add character 'e' to last_seen with index 0.

💡 Adding the first character starts building the window and tracking distinct characters.

Line:

for right, char in enumerate(s):
    if char in last_seen:
        del last_seen[char]
    last_seen[char] = right

💡 The window now contains one character 'e', which is within the allowed distinct count k=2.

expand

Expand window to include 'c' at index 1

Move right pointer to 1 and add character 'c' to last_seen with index 1.

💡 Adding a new distinct character increases the window size while still respecting the limit k=2.

Line:

for right, char in enumerate(s):
    if char in last_seen:
        del last_seen[char]
    last_seen[char] = right

💡 Window now contains 'e' and 'c', two distinct characters, which is allowed.

expand

Expand window to include 'e' at index 2 and update last_seen

Move right pointer to 2. Character 'e' is already in last_seen, so remove old entry and add new index 2.

💡 Updating last_seen for repeated characters keeps track of their most recent position for accurate window shrinking.

Line:

if char in last_seen:
    del last_seen[char]
last_seen[char] = right

💡 The window still contains only 'e' and 'c', but 'e' last seen index is updated to 2.

expand

Expand window to include 'b' at index 3, exceeding k distinct

Move right pointer to 3 and add 'b' to last_seen. Now last_seen has 3 distinct characters, exceeding k=2.

💡 Adding a new distinct character triggers the need to shrink the window to maintain the constraint.

Line:

last_seen[char] = right
if len(last_seen) > k:

💡 The window must shrink by removing the leftmost character to restore at most k distinct characters.

shrink

Shrink window by removing leftmost character 'e'

Pop the leftmost character 'e' from last_seen and move left pointer to index 1 (one past last 'e' at 0).

💡 Removing the oldest character restores the distinct character count to k=2 and shrinks the window.

Line:

_, idx = last_seen.popitem(last=False)
left = idx + 1

💡 The window now excludes the first 'e', starting at index 1, and contains 'c' and 'b'.

expand

Expand window to include 'a' at index 4, exceeding k distinct again

Move right pointer to 4 and add 'a' to last_seen. Now last_seen has 3 distinct characters again.

💡 Adding another new distinct character triggers another shrink operation.

Line:

last_seen[char] = right
if len(last_seen) > k:

💡 The window must shrink again to maintain at most 2 distinct characters.

shrink

Shrink window by removing leftmost character 'c'

Pop the leftmost character 'c' from last_seen and move left pointer to index 2 (one past last 'c' at 1).

💡 Removing 'c' restores the distinct character count to 2 and shrinks the window.

Line:

_, idx = last_seen.popitem(last=False)
left = idx + 1

💡 Window now contains 'e', 'b', and 'a' starting at index 2, but since 'e' and 'b' are distinct, window is valid.

record_answer

Update max_length after final window adjustment

Calculate current window length (right - left + 1 = 3) and update max_length if larger.

💡 Tracking the longest valid substring length ensures the correct answer is found.

Line:

max_length = max(max_length, right - left + 1)

💡 The longest substring found so far has length 3, which matches 'ece'.

reconstruct

End of string reached, return max_length

All characters processed. The maximum length of substring with at most 2 distinct characters is 3.

💡 The algorithm terminates with the correct longest substring length.

Line:

return max_length

💡 The final answer is 3, corresponding to substring 'ece'.

from collections import OrderedDict

def length_of_longest_substring_k_distinct(s: str, k: int) -> int:
    if k == 0 or not s:
        return 0
    left = 0  # STEP 1
    max_length = 0  # STEP 1
    last_seen = OrderedDict()  # STEP 1
    for right, char in enumerate(s):  # STEP 2+ loop
        if char in last_seen:  # STEP 4
            del last_seen[char]  # STEP 4
        last_seen[char] = right  # STEP 2-5
        if len(last_seen) > k:  # STEP 5-7
            _, idx = last_seen.popitem(last=False)  # STEP 6
            left = idx + 1  # STEP 6
        max_length = max(max_length, right - left + 1)  # STEP 9
    return max_length  # STEP 10

📊

Longest Substring with At Most K Distinct Characters - Watch the Algorithm Execute, Step by Step

Watching the window boundaries and the dictionary of last seen characters update in real time reveals how the algorithm efficiently manages the substring constraints without redundant checks.

expand

L ▼

e

0

c

1

e

2

b

3

a

4

Metric: 0

Answer: 0

expand

L=R

e

0

c

1

e

2

b

3

a

4

Window: [e]

Metric: 1

Answer: 1

expand

L ▼

e

0

R ▼

c

1

e

2

b

3

a

4

Window: [e, c]

Metric: 2

Answer: 2

expand

L ▼

e

0

c

1

R ▼

e

2

b

3

a

4

Window: [e, c, e]

Metric: 3

Answer: 3

expand

L ▼

e

0

c

1

e

2

R ▼

b

3

a

4

Window: [e, c, e, b]

Metric: 4

Answer: 3

shrink

e

0

L ▼

c

1

e

2

R ▼

b

3

a

4

Window: [c, e, b]

Metric: 3

Answer: 3

expand

e

0

L ▼

c

1

e

2

b

3

R ▼

a

4

Window: [c, e, b, a]

Metric: 4

Answer: 3

shrink

e

0

c

1

L ▼

e

2

b

3

R ▼

a

4

Window: [e, b, a]

Metric: 3

Answer: 3

record_answer

e

0

c

1

L ▼

e

2

b

3

R ▼

a

4

Window: [e, b, a]

Metric: 3

Answer: 3

record_answer

L ▼

e

0

c

1

R ▼

e

2

b

3

a

4

Window: [e, c, e]

Metric: 3

Answer: 3

Key Takeaways

✓ The sliding window dynamically expands and shrinks to maintain at most k distinct characters efficiently.

This dynamic adjustment is hard to grasp from code alone but becomes clear when watching the window boundaries move step-by-step.

✓ The ordered dictionary (or equivalent) tracks the last seen indices of characters to know exactly which character to remove when shrinking.

Understanding this data structure's role clarifies why the left pointer jumps past the correct index instead of moving one by one.

✓ Updating the max_length only when a longer valid window is found ensures the algorithm returns the correct longest substring length.

Seeing the max_length update in real time helps connect the window size to the final answer.

Practice

1. Consider the following Python code implementing the sliding window with count matching optimization to find all anagrams of p in s. What is the final returned list when s = "cbaebabacd" and p = "abc"?

easy

A. [0, 1, 6]

B. [0, 6, 7]

C. [0, 6, 8]

D. [0, 6]

Solution

1. Step 1: Trace first window (indices 0 to 2)

   Substring "cba" is an anagram of "abc", so index 0 is added.

2. Step 2: Slide window and check matches

   Next valid anagram found at index 6 ("bac"). No other windows match all counts.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Known example output matches [0, 6] [OK]

Hint: Anagrams appear at indices 0 and 6 only [OK]

Common Mistakes:

• Including indices where substring is not full anagram
• Off-by-one errors in window boundaries

2. You are given a string and need to find the length of the longest substring where no character repeats. Which approach guarantees an optimal solution with linear time complexity?

easy

A. Brute force checking all substrings and verifying uniqueness by sorting each substring

B. Sliding window with a hash map tracking the last seen index of each character to dynamically adjust the window

C. Dynamic programming by storing longest substring lengths ending at each index without duplicates

D. Greedy approach by always extending the substring until a duplicate is found, then restarting from next character

Solution

1. Step 1: Understand problem constraints

   The problem requires finding the longest substring without repeating characters, which suggests a variable-size window to track unique characters efficiently.

2. Step 2: Evaluate approaches

   Brute force and greedy approaches either have high time complexity or fail to adjust the window correctly. Dynamic programming is not straightforward here. The sliding window with a hash map efficiently tracks last seen indices and adjusts the window in O(n) time.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Sliding window with index tracking is the known optimal pattern [OK]

Hint: Sliding window with index map -> O(n) solution [OK]

Common Mistakes:

• Confusing greedy restart with sliding window
• Using DP without clear state definition

3. The following code attempts to find all anagrams of p in s using a sliding window with count matching optimization. Which line contains a subtle bug that can cause incorrect results or runtime errors?

medium

A. Line missing decrement of window_count[left_index] when shrinking window

B. Line checking if window_count[index] == p_count[index] + 1 to decrement matches

C. Line incrementing window_count[index] when adding right character

D. Line appending left index to result when matches == 26

Solution

1. Step 1: Identify window shrinking logic

   When window size exceeds p length, left character count must be decremented.

2. Step 2: Locate missing decrement

   The code does not decrement window_count[left_index] before moving left pointer, causing incorrect counts.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Missing decrement breaks frequency tracking [OK]

Hint: Always decrement count when shrinking window [OK]

Common Mistakes:

• Forgetting to decrement frequency on window shrink
• Incorrect matches update logic
• Appending wrong indices

4. Suppose the problem changes: now you want to find the maximum average subarray of size at most k (i.e., any size from 1 up to k). Which approach correctly adapts the sliding window technique to solve this efficiently?

hard

A. Use nested loops to check all subarrays of size 1 to k, recomputing sums each time

B. Use a sliding window of size k and track max average for all smaller windows by shrinking the window dynamically

C. Use prefix sums to compute sums of all subarrays up to size k in O(n) time

D. Use a sliding window for each size from 1 to k separately, then take the maximum average found

Solution

1. Step 1: Understand problem change

   Now subarray size can vary from 1 to k, so fixed-size sliding window alone is insufficient.

2. Step 2: Evaluate approaches

   Use a sliding window for each size from 1 to k separately, then take the maximum average found runs sliding window for each size from 1 to k, each in O(n), total O(n*k), which is efficient and correct. Using a sliding window of size k and tracking max average for all smaller windows by shrinking the window dynamically is incorrect because shrinking window dynamically breaks fixed-size window assumptions. Using prefix sums to compute sums of all subarrays up to size k in O(n) time is incorrect as prefix sums alone do not reduce complexity below O(n*k). Using nested loops to check all subarrays of size 1 to k, recomputing sums each time is naive and inefficient.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Sliding window repeated for each size is correct and efficient [OK]

Hint: Sliding window works per fixed size; vary size by repeating windows [OK]

Common Mistakes:

• Trying to shrink window dynamically breaking fixed size
• Assuming prefix sums alone solve all size ranges efficiently

5. Suppose the problem is modified so that characters in s1 can be reused multiple times in the substring of s2 (i.e., the substring can contain repeated characters beyond the counts in s1). Which modification to the sliding window approach correctly handles this variant?

hard

A. Remove the match count optimization and compare frequency maps at every window slide to allow repeated characters.

B. Keep the same sliding window with frequency counts and match count, but ignore counts exceeding those in s1.

C. Use a sliding window that only checks if all characters in s1 appear at least once in the window, ignoring exact counts.

D. Modify the algorithm to only check if the window contains all unique characters of s1 regardless of frequency.

Solution

1. Step 1: Understand the variant

   Allowing reuse means the substring can have more occurrences of characters than in s1. The previous match count optimization relies on exact frequency matches, which no longer applies.

2. Step 2: Identify correct approach

   To handle repeated characters beyond s1 counts, the algorithm must compare full frequency maps at each window slide, since match count optimization assumes exact matches.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Match count optimization breaks if counts can exceed s1 counts [OK]

Hint: Exact frequency match optimization fails if counts can exceed s1 [OK]

Common Mistakes:

• Assuming match count optimization still works
• Ignoring frequency counts and only checking presence