PPractick

The problem

A compression engine gets its best ratios on stretches of text that use few distinct characters. Given a string and k, find the length of the longest substring with at most k distinct characters. It's the general version of "fruit into baskets" (k = 2): grow a window on the right while counting characters, and when the number of distinct characters exceeds k, shrink from the left until one character's count drops to zero.

Example: s = "eceba", k = 2 → 3 ("ece").

Function signature

int lengthOfLongestSubstringKDistinct(const string& s, int k);

Test cases

Input (s, k)	Output	Explanation
("eceba", 2)	3	"ece"
("aa", 1)	2
("aabacbebebe", 3)	7	"cbebebe"
("abaccc", 2)	4	"accc"
("abc", 0)	0	No characters allowed

(Confirm: substring means contiguous; k ≥ 0; characters are arbitrary bytes.)

How interviewers phrase it

• "Given a string s and an integer k, return the length of the longest substring that contains at most k distinct characters" (LeetCode 340).

Clarifying questions to ask

1. At most k, not exactly k? (At most.)
2. Can k be 0? (Yes, and the answer is 0.)
3. What's the character set? (A 256-entry count array handles bytes.)

Follow-ups to expect

1. "How do you count distinct characters in O(1)?"
2. "Why does the left pointer never move back?"
3. "What about exactly k distinct?"
4. "Streaming with bounded memory?"
5. "Complexity?"

Related questions

• Longest Repeating Character Replacement Hard
• Minimum Window Substring Hard
• Number of Substrings Containing All Three Characters Hard
• Minimum Window Subsequence Hard
• Isomorphic String Easy
• Check if two strings are anagram of each other Easy

All 474 dsa interview questions

DSA mock interviews · System design interview questions · Free mock interview practice · Browse interviewers · Sign in