DSA problem
Longest Substring with At Most K Distinct Characters
Given a string s and an integer k, return the length of the longest substring of s that contains at most k distinct characters.
A substring is a contiguous, non-empty sequence of characters within a string. If k is 0, no character is allowed, so the answer is 0.
This is a classic variable-size sliding window problem. As you expand a window to the right, you track how many distinct characters it currently holds. Whenever that count exceeds k, you shrink the window from the left until the constraint is satisfied again, recording the maximum valid window length along the way.
Examples
Example 1
Input:
s = "eceba", k = 2Output:
3Explanation: The substring "ece" has length 3 and contains exactly 2 distinct characters ("e" and "c"). No valid substring of length 4 exists.
Example 2
Input:
s = "aa", k = 1Output:
2Explanation: The substring "aa" has length 2 and contains exactly 1 distinct character.
Example 3
Input:
s = "abcadcacacaca", k = 3Output:
11Explanation: The substring "cadcacacaca" has length 11 and contains 3 distinct characters ("a", "c", "d").
Constraints
- 1 <= s.length <= 5 * 10^4
- 0 <= k <= 50
- s consists of English letters.
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.