← DiffPush

Longest Substring with At Most K Distinct Characters

DiffPush Tier Sliding Window · Hard Problems O(n) · O(k)

The Frequency-Hopping Spectrum Plan

A radio modem hops across channels, and its log records one channel letter per timeslot. Interference rules cap a transmission burst at k distinct channels, and the firmware wants the longest burst it can legally broadcast. The planner slides a frame over the log, dropping the oldest channel each time a (k+1)-th distinct channel appears.

Input: A string s of channel letters and an integer k.

Output: Return the length of the longest substring containing at most k distinct characters.

Constraints

• 1 <= s.length <= 10^5
• 1 <= k <= 26 (lowercase English letters)

Examples

Example 1

Input: {"s":"abbbbbbc","k":2}
Output: 7
Bursts "abbbbbb" and "bbbbbbc" each use two channels across seven slots.

Example 2

Input: {"s":"abcde","k":2}
Output: 2
Every channel is distinct, so no legal burst exceeds two slots.

Solve this in your browser →

Also on LeetCode ↗