Longest Substring With At Most K Distinct

The problem

A radio station's playlist is a list of artist names, in play order. Write a function that returns the length of the longest run of consecutive songs that uses at most k different artists. k is at least 0.

text
1longest_with_k_artists(["ana", "bo", "ana", "cy", "cy", "cy"], 2)  ->  4
2longest_with_k_artists(["ana", "bo", "cy"], 1)                     ->  1
3longest_with_k_artists(["ana", "ana"], 0)                          ->  0

Example 1, k = 2

ana

Four songs in a row by just two artists.

In the first example, the run "ana", "cy", "cy", "cy" has two artists and four songs. The run "ana", "bo", "ana" is shorter.

Write longest_with_k_artists(artists, k) in Python or longestWithKArtists(artists, k) in JavaScript.

Runs privately in your browser. Nothing is sent to a server.Ctrl/⌘ + Enter to run · Esc then Tab to leave the editor

Write your function, then run it against 20 tests.

Breakdown

Stuck? Reveal one step at a time, and try again after each one.

Step 2
Step 3
Step 4

Solution

Give it a real try first: you learn far more from a wrong attempt than from reading the answer.

Use a sliding window with a map of counts. For each song, add it to the map. While the map has more than k artists, remove artists[left] from the window (deleting it from the map at zero) and move left on. Then update the best length.

python

1def longest_with_k_artists(artists, k):

2    in_window = {}  # artist -> number of their songs in the window

artist -> songs in the window

3    best = 0

4    left = 0

5    for right, artist in enumerate(artists):

6        in_window[artist] = in_window.get(artist, 0) + 1

7        while len(in_window) > k:

too many artists: shrink

8            leaving = artists[left]

9            in_window[leaving] -= 1

10            if in_window[leaving] == 0:

11                del in_window[leaving]

gone completely: remove the key

12            left += 1

13        best = max(best, right - left + 1)

valid again: record it

14    return best

Complexity

TimeO(n)SpaceO(k)

O(n) time: each song enters and leaves the window at most once. O(k) space for the map, since it never holds more than k + 1 artists.

What we learned

A map of counts lets a window answer "how many different things are inside?" in O(1).
Delete keys whose count drops to zero, or the "number of keys" stops meaning "number of artists in the window".
For "longest valid window", shrink first, then record.