Longest Substring K Distinct

Python data engineering interview problem. Difficulty: intermediate. Pattern: Sliding Window. About 14 minutes. Part of the Pro drill bank.

Longest substring with at most k distinct characters. Treat this as a production helper: match the contracted return shape, including empty and duplicate inputs.

A user session can contain many repeated page types. We want the longest continuous session segment that uses no more than a fixed number of distinct types. Return the length of the longest substring containing at most k different characters. The substring must be contiguous, and repeated copies of a character count once toward the distinct limit. Write the function length_k_distinct(s: str, k: int) -> int. In 'eceba' with k = 2, 'ece' uses only e and c and has length 3, so the answer is 3. The starter file already has the function name and the harness print lines. Keep them, and fill only the function body.

Requirements

• Track the number of distinct characters in the current window.
• Shrink from the left when the window has more than k distinct characters.
• Return the maximum length, not the substring.

Constraints

• k is a non-negative integer and the string is treated as a sequence of characters.
• The return type is int; an empty string returns 0.

Examples

Input: length_k_distinct('eceba', 2) Output: 3 ece uses two distinct letters.

Topics: lakebench, python, window, k-distinct.

More Python interview questions · All interview problems · Learn data engineering