Where it runs
1. The problem
You want the longest piece of text with at most 2 different letters. For "eceba" the answer is "ece", length 3.
In the last lesson the window kept one number, a sum. One number can't answer this question. The rule "at most 2 different letters" is about what the window holds: which letters are in it and how many of each. A sum tells you nothing about that. The window has to remember what is inside it.
A rate limiter (a program that stops a client from sending requests too often) works the same way. It asks: how many requests did this client make in the last 60 seconds? That is a count of what lies in a moving window of time right now.
2. In plain words
Now the rule is about what lies inside the run, for example "at most 2 different letters at once". One sum can't answer that. You need to know which letters are in the window and how many of each.
So you keep a count for each letter. Take "eceba". The window "ece" holds two e's and one c: 2 different letters, which is fine. Add b, and there are 3 different letters. So remove letters on the left until one letter is gone from the window completely. Remove the first e: one e is left, still 3 different letters. Remove c: its count drops to 0, so c is out of the window. Now there are 2 different letters again. The number of different letters in your counts is what you check against the rule as you grow and shrink the window.
3. The idea
Keep a Map (a table of key → count, from the lesson on Map) for the elements that are in the window right now. When right adds an element to the window, increase its count. When left removes an element, decrease its count. If a count reaches zero, delete the key. Then map.size (the number of keys in the Map) equals the number of different values in the window. That is the number you check against the rule.
Deleting the key at zero is required. Say a key with count 0 stays in the Map. Then map.size counts a letter that is no longer in the window. The check on the number of different letters goes wrong, and the window gets wider than allowed.
The order is this. Move right and increase the count. While the window has too many different values, remove the element on the left and decrease its count, deleting the key at zero. When the rule holds again, write down the window length.
Trace "the longest run with at most 2 different letters" on "eceba".
- Add e:
{e:1}, length 1. - Add c:
{e:1, c:1}, length 2. - Add e:
{e:2, c:1}, length 3 ("ece"). - Add b: now 3 different letters. Remove the e on the left:
{e:1, c:1, b:1}, still 3 different. Remove c:{e:1, b:1}, 2 different. The window is"eb", length 2. - Add a: 3 different letters again. Remove e:
{b:1, a:1}. The window is"ba", length 2.
The best length is 3.
4. What it costs
Time is O(n). right adds each element once, and left removes each at most once. Each Map operation takes about one step. Memory is O(K): the Map holds no more keys than the number of different values the window may have. That number is bounded by K or by the size of the alphabet (the number of all possible letters).
6. Where this shows up
API rate limiters and abuse protection keep counters in a sliding window for each client or address. Monitoring watches a rule such as "at most K different users or IP addresses per window". The search for the longest substring without repeats uses the same window with a stricter rule. When a decision for a moving window depends on which elements it holds and how many of each, the window keeps a Map this way.
Recognise it
Say these words and it is this pattern
- longest/shortest contiguous subarray or substring
- satisfying a condition (sum <= K, at most, without breaking a limit)
- at most K distinct, no repeated element, contains all of X
- contiguous span, not a subsequence
Looks similar, isn't
- Sliding window (fixed size)
A fixed window is k wide from the first step to the last. This one picks its own width.
- Two pointers (opposite ends)
Those start apart on sorted data and converge to one pair. Here both ends move the same way.
- Prefix sums
Prefix sums handle negative values and arbitrary ranges. Shrinking assumes removing a value helps.
- Hash set / map
A map on its own describes the whole collection. The window needs counts for the live span.
n up to 1e6 and one best span gives O(n). Each end advances at most n times.
On LeetCode
Problems about the longest or shortest substring or subarray whose rule depends on what is inside, such as no repeats, at most k different values, or every needed letter. The window keeps a count of each value in a Map.
Keep the last k numbers in a Set and ask whether the new number is already there.
The lesson task with k = 2, told as fruit types instead of letters.
Shrink from the left until the letter that just came in has a count of 1 again.
The window fits while its length minus the count of its most common letter is at most k.
Grow until every needed letter is covered, then shrink from the left to the shortest window that still covers them.
Your task (Tier 1)
Write the function longestAtMostKDistinct(s, K).
Find the longest run of letters in a row with at most K different letters. Keep a count of each letter in the window, and shrink the window on the left when there are too many different letters.
- Input:
s, a string, andK, how many different letters are allowed at once. Example:"eceba",2. - Return: the length of the longest run with at most
Kdifferent letters.
Steps:
- Make an empty map
count(letter -> how many times it occurs in the window), a markerleft = 0and a best lengthbest = 0. - Move
rightacross the string. Add 1 to the count of the letters[right]. - While the map holds more than
Kdifferent letters, subtract 1 from the count ofs[left]. If that count reaches0, remove the letter from the map. Moveleftone step right. - If the window length
right - left + 1is bigger thanbest, updatebest. At the end, returnbest.
Done when all tests pass:
"eceba",2->3("ece")"aa",1->2"abcabc",2->2"aabb",5->4(Kis bigger than the number of different letters in the string)"aaabbb",1->3"abc",0->0(no letter is allowed)"",2->0(empty string)"a",1->1
Practice
longestAtMostKDistinct
longestAtMostKDistinct(s, K) -> number (length of longest substring of s with at most K distinct characters)
export function longestAtMostKDistinct(s, K) {
// Your code here. The task is described in the box above the editor.
}
Running as a guest
The tests run right here, no account needed. Your code is kept in this browser only. A free account keeps it on every device, marks the step done and shows where you are in the course.
Hint ladder
Stuck? Reveal one rung at a time, but try it yourself first.