MediumHash TableStringSliding Window

Longest Substring with At Most K Distinct Characters

1 approach, code in every language

Given a string s and an integer k, find the length of the longest contiguous substring that contains no more than k distinct characters.

If k is zero, no characters may appear, so the answer is zero.

Example 1

Input: s = "eceba", k = 2

Output: 3

The block "ece" uses only the two distinct characters e and c.

Example 2

Input: s = "aabbcc", k = 1

Output: 2

With only one distinct character allowed, a run like "aa" is the longest possible.

Constraints

1 <= s.length <= 5 * 10^4
0 <= k <= 5 * 10^4
s consists of English letters.

Sliding window with a frequency map

Extend the window to the right, and whenever the number of distinct characters exceeds k, retract the left edge until the count returns to k.

Loading animation…

Intuition

The set of distinct characters inside the window only grows when the right edge adds a brand-new character and only shrinks when the left edge drops the last copy of a character. By keeping counts in a map, the size of that map is exactly the distinct count. Whenever it overshoots k, moving the left edge forward and deleting exhausted entries restores a legal window, and the largest legal width seen along the way is the answer.

Algorithm walkthrough

1Maintain a map of character to count for the current window and a left pointer at the start.
2Advance the right pointer, incrementing the count of the incoming character.
3While the map holds more than k distinct keys, decrement the left character's count and remove it from the map when it reaches zero, moving left forward.
4After each adjustment, update the best length with the current window width.
5Return the best width found, which is zero when k is zero.

Implementation

class Solution:
    def lengthOfLongestSubstringKDistinct(self, s: str, k: int) -> int:
        if k == 0:
            return 0
        count = {}
        left = 0
        best = 0
        for right, ch in enumerate(s):
            count[ch] = count.get(ch, 0) + 1
            while len(count) > k:
                lc = s[left]
                count[lc] -= 1
                if count[lc] == 0:
                    del count[lc]
                left += 1
            best = max(best, right - left + 1)
        return best

Time

O(n)

Space

O(k)

The map never holds more than k + 1 keys during processing.

Create a free account to see the solution

You get the step-by-step animation, the intuition and clean code in every language. Free, no credit card.

Create a free account Already have an account? Sign in

Back to Strings

After the pattern

Now solve one you haven't seen.

Longest Belt Run Within a Colour Budget is our own problem on the technique behind Longest Substring with At Most K Distinct Characters: a new statement, so there's no answer to remember. Write it in your browser and run it against graded tests.

Practise it with tests All practice problems

1,194 problems · 15,062 graded tests · free