Find the Longest Stretch of a Playlist With No Artist Twice

Restarting after every repeat reads the same songs again; moving the left edge past the earlier copy reads each song once.

A variable window with a map from each item to its last position finds the longest run with no repeated item in one pass. A playlist plays songs by the artists A B C A D B E, in that order, and the listener wants the longest stretch of consecutive songs in which no artist plays twice.

The brute force tries every starting song and extends it with a set of the artists seen until an artist repeats. Each start can read the rest of the playlist, so the cost is O(n²) for n songs. The repeated work is in the restarts: after the repeat of A at position 3, the attempt starting at B reads B, C and A again, though the first attempt already showed those three hold no repeat.

The window keeps that knowledge. End moves one song at a time, and a map records the last position of every artist. When the artist at end already appears inside the window, start jumps to the position after that earlier copy, which removes the repeat and keeps every song after it. Start must never move left, so the jump is to max(start, last + 1): an artist last seen before the window began is not a repeat.

The playlist A B C A D B E with a map of last positions

Inputartists A B C A D B E

End 0
1. Astartend
2. B
3. C
4. A
5. D
6. B
7. E
A is new: window A, best 1
End 1
1. Astart
2. Bend
3. C
4. A
5. D
6. B
7. E
B is new: window A B, best 2
End 2
1. Astart
2. B
3. Cend
4. A
5. D
6. B
7. E
C is new: window A B C, best 3
End 3
1. A
2. Bstart
3. C
4. Aend
5. D
6. B
7. E
A last at 0, start moves to 1: window B C A, best 3
End 4
1. A
2. Bstart
3. C
4. A
5. Dend
6. B
7. E
D is new: window B C A D, best 4
End 5
1. A
2. B
3. Cstart
4. A
5. D
6. Bend
7. E
B last at 1, start moves to 2: window C A D B, best 4
End 6
1. A
2. B
3. Cstart
4. A
5. D
6. B
7. Eend
E is new: window C A D B E, best 5

ResultThe longest stretch is C A D B E, 5 songs.

The listing runs both versions on the playlist and counts the songs each reads, then runs the window on a playlist of one artist and on an empty one.

playlist.pypy

def longest_by_restarting(songs: list[str]) -> tuple[int, int]:
    best = reads = 0
    for i in range(len(songs)):
        seen: set[str] = set()
        for j in range(i, len(songs)):
            reads += 1
            if songs[j] in seen:
                break
            seen.add(songs[j])
        best = max(best, len(seen))
    return best, reads


def longest_window(songs: list[str]) -> tuple[int, int]:
    last: dict[str, int] = {}
    start = best = best_start = 0
    for end, artist in enumerate(songs):
        start = max(start, last.get(artist, -1) + 1)
        last[artist] = end
        if end - start + 1 > best:
            best, best_start = end - start + 1, start
    return best, best_start


playlist = "A B C A D B E".split()
best, reads = longest_by_restarting(playlist)
print(f"restarting: longest {best} ({reads} songs read)")
best, first = longest_window(playlist)
print(f"window: longest {best},", *playlist[first:first + best], f"({len(playlist)} songs read)")
print("one artist only:", longest_window(["A", "A", "A"])[0])
print("empty playlist:", longest_window([])[0])

OutputRan with python:3.14.8-slim-trixie (Python 3.14.8)

restarting: longest 5 (24 songs read)
window: longest 5, C A D B E (7 songs read)
one artist only: 1
empty playlist: 0

Restarting read 24 songs to find the answer the window found in 7. The window costs O(n) time and O(k) extra space for k distinct artists, since the map holds one entry per artist. The same pass finds the longest run of a string with no repeated character, where the map's keys are characters.

Sliding Window

← → move through sections and cards