Longest Substring with At Most K Distinct Characters

📋

Problem

Imagine you're analyzing a stream of characters from a social media feed and want to find the longest segment where the diversity of topics (characters) is limited to at most K distinct ones.

Given a string s and an integer k, find the length of the longest substring of s that contains at most k distinct characters. Return the length of such substring.

1 ≤ s.length ≤ 10^50 ≤ k ≤ s.lengths consists of English letters, digits, symbols, and spaces.

Edge cases: k = 0 → output should be 0 because no characters alloweds is empty string → output should be 0k >= length of s → output should be length of s

</>

IDE

def length_of_longest_substring_k_distinct(s: str, k: int) -> int:public int lengthOfLongestSubstringKDistinct(String s, int k)int lengthOfLongestSubstringKDistinct(string s, int k)function lengthOfLongestSubstringKDistinct(s, k)

def length_of_longest_substring_k_distinct(s: str, k: int) -> int:
    # Write your solution here
    pass

class Solution {
    public int lengthOfLongestSubstringKDistinct(String s, int k) {
        // Write your solution here
        return 0;
    }
}

#include <string>
using namespace std;

int lengthOfLongestSubstringKDistinct(string s, int k) {
    // Write your solution here
    return 0;
}

function lengthOfLongestSubstringKDistinct(s, k) {
    // Write your solution here
}

Common Bugs to Avoid

Wrong: 0Returning 0 when k > 0 and s is non-empty due to not updating max length.✅ Initialize max length to 0 and update it whenever window is valid.

Wrong: length of longest substring with exactly k distinct charsMisunderstanding problem requirement; counting substrings with exactly k distinct chars instead of at most k.✅ Allow window with distinct chars count <= k, not just == k.

Wrong: length of longest substring with distinct chars <= k but not shrinking window properlyNot shrinking window when distinct chars exceed k, causing incorrect max length.✅ Shrink window from left until distinct chars count <= k.

Wrong: length off by one (too small)Off-by-one error in window boundaries or max length update timing.✅ Update max length after adjusting window boundaries correctly.

Wrong: TLEUsing brute force O(n^2) approach on large inputs.✅ Implement sliding window with frequency map for O(n) time complexity.

✓

Test Cases

Focus on handling empty and minimal inputs correctly.

Watch out for subtle bugs like off-by-one and greedy traps.

Optimize your solution to linear time using sliding window technique.

t1_01basic

Input{"s":"eceba","k":2}

Expected3

⏱ Performance - must finish in 2000ms

The longest substring with at most 2 distinct characters is 'ece' with length 3.

💡 Use a sliding window to track characters and their counts.

💡 Maintain a frequency map and shrink the window when distinct chars exceed k.

💡 Update max length when window is valid; remove chars when count hits zero.

Why it failed: Returned incorrect length; likely not shrinking window when distinct chars exceed k. Fix by decrementing counts and moving left pointer until distinct chars <= k.

✓ Correctly handles the canonical example with sliding window and frequency map.

t1_02basic

Input{"s":"aaabbcc","k":2}

Expected5

⏱ Performance - must finish in 2000ms

Longest substring with at most 2 distinct chars is 'aaabb' or 'abbcc' with length 5.

💡 Try expanding window while distinct chars <= k.

💡 When distinct chars exceed k, shrink from left until valid.

💡 Track max length during valid windows.

Why it failed: Incorrect output due to not properly updating max length after shrinking window. Fix by updating max length only when window is valid.

✓ Correctly finds longest substring length with at most 2 distinct characters.

t2_01edge

Input{"s":"","k":0}

Expected0

⏱ Performance - must finish in 2000ms

Empty string input returns 0 regardless of k.

💡 Check for empty input string as a base case.

💡 If string is empty, longest substring length is 0.

💡 Return 0 immediately if s is empty.

Why it failed: Fails empty string case; likely does not handle empty input. Fix by returning 0 if s is empty.

✓ Correctly returns 0 for empty string input.

t2_02edge

Input{"s":"a","k":1}

Expected1

⏱ Performance - must finish in 2000ms

Single character string with k=1 returns length 1.

💡 Test minimal non-empty string with k=1.

💡 Window can include the single character since distinct chars <= k.

💡 Max length should be 1.

Why it failed: Fails single element case; possibly off-by-one error or incorrect initialization. Fix by initializing max length to at least 1 when s non-empty and k >= 1.

✓ Correctly handles single character string with k=1.

t2_03edge

Input{"s":"abcde","k":5}

Expected5

⏱ Performance - must finish in 2000ms

k equals string length, so entire string is valid substring.

💡 If k >= length of s, entire string is valid.

💡 Check if your code handles this boundary correctly.

💡 Max length should be length of s.

Why it failed: Fails boundary where k equals string length; likely does not handle k >= s.length correctly. Fix by returning s.length if k >= s.length.

✓ Correctly returns full string length when k >= s.length.

t3_01corner

Input{"s":"aabbcc","k":1}

Expected2

⏱ Performance - must finish in 2000ms

Longest substring with at most 1 distinct char is 'aa', 'bb', or 'cc' length 2.

💡 Check if your code mistakenly allows more than k distinct chars.

💡 Verify frequency map updates and window shrinking logic.

💡 Ensure window shrinks until distinct chars <= k.

Why it failed: Fails greedy trap by not shrinking window properly when distinct chars exceed k. Fix by moving left pointer and updating counts until distinct chars <= k.

✓ Correctly handles greedy trap by maintaining valid window size.

t3_02corner

Input{"s":"abcabcabc","k":2}

Expected2

⏱ Performance - must finish in 2000ms

Longest substring with at most 2 distinct chars is any two consecutive chars, length 2.

💡 Check if your code mistakenly counts substrings with more than k distinct chars.

💡 Verify that window shrinks correctly when distinct chars exceed k.

💡 Update max length only when window is valid.

Why it failed: Fails 0/1 vs unbounded confusion by allowing substrings with more than k distinct chars. Fix by enforcing window shrink until distinct chars <= k.

✓ Correctly enforces at most k distinct chars in window.

t3_03corner

Input{"s":"abaccc","k":2}

Expected4

⏱ Performance - must finish in 2000ms

Longest substring with at most 2 distinct chars is 'accc' length 4.

💡 Check off-by-one errors in window boundaries.

💡 Ensure max length updates after each valid window adjustment.

💡 Verify frequency map decrements and removals.

Why it failed: Fails off-by-one error causing max length to be underestimated. Fix by updating max length after adjusting window boundaries correctly.

✓ Correctly handles off-by-one window boundary updates.

t4_01performance

Input{"_description":"n=100000 at constraint boundary - executor generates this"}

Expectednull

⏱ Performance - must finish in 2000ms

Input size n=100000 requires O(n) solution to complete within 2 seconds.

💡 Brute force O(n^2) will time out on large inputs.

💡 Use sliding window with frequency map for O(n) time complexity.

💡 Avoid nested loops and redundant substring checks.

Why it failed: TLE due to O(n^2) brute force approach. Fix by implementing O(n) sliding window with frequency map.

✓ Solution runs in O(n) time confirming efficient sliding window approach.

Practice

1. Consider the following Python code implementing the optimal solution for the problem. What is the returned value when calling longestOnes([1,0,1,0], 1)?

from collections import deque

def longestOnes(nums, k):
    zero_positions = deque()
    left = 0
    max_length = 0
    for right in range(len(nums)):
        if nums[right] == 0:
            zero_positions.append(right)
        if len(zero_positions) > k:
            left = zero_positions.popleft() + 1
        max_length = max(max_length, right - left + 1)
    return max_length

easy

A. 4

B. 2

C. 1

D. 3

Solution

1. Step 1: Trace iterations with input [1,0,1,0], k=1

   Right=0: nums[0]=1, zero_positions=[], max_length=1 Right=1: nums[1]=0, zero_positions=[1], max_length=2 Right=2: nums[2]=1, zero_positions=[1], max_length=3 Right=3: nums[3]=0, zero_positions=[1,3], length=2 > k=1 triggers left update left = zero_positions.popleft()+1 = 1+1=2, zero_positions=[3], max_length remains 3

2. Step 2: Final max_length after loop ends is 3

   The longest subarray with at most 1 zero flipped is length 3.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Manual trace confirms max_length=3 [OK]

Hint: Track zero positions and window boundaries carefully [OK]

Common Mistakes:

• Off-by-one errors in window length
• Not updating left pointer correctly
• Confusing max_length update timing

2. You are given an array of positive integers and a target sum. You need to find the length of the smallest contiguous subarray whose sum is at least the target. Which algorithmic approach guarantees an optimal O(n) time solution for this problem?

easy

A. Brute force nested loops checking all subarrays

B. Sorting the array and using binary search for subarray sums

C. Dynamic programming with memoization over subarray sums

D. Sliding window with two pointers adjusting window size dynamically

Solution

1. Step 1: Understand problem constraints

   The problem requires finding the minimal length subarray with sum ≥ target, which suggests a variable-size window approach.

2. Step 2: Identify algorithm that adjusts window size efficiently

   Sliding window with two pointers can expand and shrink the window in O(n) time, ensuring minimal length is found without checking all subarrays.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Sliding window is known for O(n) minimal subarray sum solutions [OK]

Hint: Minimal subarray sum -> variable-size sliding window [OK]

Common Mistakes:

• Thinking sorting helps with contiguous subarrays
• Assuming DP is needed for minimal length
• Using brute force for optimality

3. Consider the following Python function implementing the sliding window approach to find the minimum size subarray sum. What is the returned value when calling min_subarray_len(5, [1,2,3,4])?

def min_subarray_len(target, nums):
    n = len(nums)
    left = 0
    current_sum = 0
    min_length = float('inf')
    for right in range(n):
        current_sum += nums[right]
        while current_sum >= target:
            min_length = min(min_length, right - left + 1)
            current_sum -= nums[left]
            left += 1
    return 0 if min_length == float('inf') else min_length

easy

A. 1

B. 2

C. 3

D. 4

Solution

1. Step 1: Trace iterations and sums

   Right=0: sum=1 (less than 5), Right=1: sum=3 (less than 5), Right=2: sum=6 (≥5), update min_length=3, shrink window: sum=6-1=5, left=1, update min_length=2, shrink again: sum=5-2=3 (less than 5), stop shrinking.

2. Step 2: Continue to Right=3

   sum=3+4=7 (≥5), update min_length=min(2,3)=2, shrink: sum=7-3=4 (less than 5), stop shrinking.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Minimal subarray length with sum≥5 is 2 ([2,3] or [4]) [OK]

Hint: Shrink window while sum ≥ target to find minimal length [OK]

Common Mistakes:

• Off-by-one in window length calculation
• Not shrinking window properly
• Returning min_length without checking infinity

4. 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

5. What is the time complexity of the optimized sliding window algorithm that uses a hash map to track the last seen indices of characters for finding the longest substring without repeating characters?

medium

A. O(n) because each character is visited at most twice by the right and left pointers

B. O(n^2) because each character may cause the left pointer to move multiple times

C. O(n log n) due to hash map operations on each character

D. O(n * m) where m is the size of the character set

Solution

1. Step 1: Analyze pointer movements

   Right pointer moves forward once per character. Left pointer only moves forward when duplicates are found, never backward. Each character is visited at most twice.

2. Step 2: Consider hash map operations

   Hash map lookups and updates are O(1) average. Thus total time is O(n).

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Two-pointer sliding window with hash map -> linear time [OK]

Hint: Each character visited max twice -> O(n) [OK]

Common Mistakes:

• Assuming nested loops cause O(n^2)
• Confusing hash map average with worst-case