Longest Substring with At Most K Distinct Characters

You are given a lowercase string s and an integer k. Find the length of the longest substring of s that contains at most k distinct characters.

Input: The first line contains the string s. The second line contains the integer k. Output: Print a single integer: the length of the longest substring of s with at most k distinct characters.

1 <= |s| <= 10^5 0 <= k <= 26 s consists only of lowercase English letters.

This is the SAME sliding-window-plus-hash-map technique as the identically-titled Hashing-category problem - the underlying algorithm doesn't change based on which category a problem is filed under.

Find the longest substring containing no more than k distinct characters. Brute force: Check every possible substring directly, counting its distinct characters - this costs O(n²) or worse, too slow for large strings. Optimised: A sliding window with a frequency map lets both the expand (right) and shrink (left) operations happen in a SINGLE combined linear pass - every character enters and leaves the window at most once across the whole algorithm, giving true O(n) total work.

1. Maintain a frequency count of characters CURRENTLY inside the window, and track how many DISTINCT characters it holds. 2. Expand the window one character at a time on the right; whenever the distinct count EXCEEDS k, shrink from the left (decrementing counts, removing zero-count entries) until it's at most k again. 3. Track the maximum window length seen after each expansion.

Time: O(n) - each character enters and leaves the window at most once. Space: O(k) or O(alphabet size), for the frequency map of characters currently in the window.

Handle k = 0 (no substring is allowed to have any character, so the answer is 0) and k >= 26 (the whole string always qualifies, so the answer is |s|).

Be ready to connect this directly to 'Longest Substring Without Repeating Characters' (which is exactly this problem with k=1) - recognizing that one problem generalizes another is valuable pattern recognition.