A tasting counter serves dishes in order; menu is a lowercase string where each letter is a flavour. A guest can handle at most k different flavours in one sitting. Return the length of the longest contiguous stretch of dishes containing at most k distinct flavours.
Examples
Input: menu = "eceba", k = 2
Output: 3
Explanation: "ece" uses only flavours e and c.
Input: menu = "aa", k = 1
Output: 2
Input: menu = "abc", k = 0
Output: 0
Constraints
0 <= len(menu) <= 10**5,0 <= k <= 26menuconsists of lowercase English letters.- Target complexity: O(n) time; building a set for every substring is far too slow for the largest tests.
Goals
- Maintain a frequency map and the number of distinct keys in the window
- Shrink the window when the distinct count exceeds the limit