Number of Music Playlists

Number of Music Playlists

What is this problem about?

The Number of Music Playlists problem asks you to count distinct playlists of exactly goal songs using n unique songs, where: every song must be played at least once, and a song cannot be replayed unless at least k other songs have been played since its last play. Return the count modulo 10^9+7. This hard coding problem uses combinatorial DP.

Why is this asked in interviews?

Coursera and Google ask this hard problem because it requires precise DP state design capturing the number of songs used so far and the current playlist length, combined with careful counting of when a previously-heard song can be repeated. The math, combinatorics, and dynamic programming interview pattern is comprehensively tested.

Algorithmic pattern used

2D DP. dp[i][j] = number of playlists of length i using exactly j unique songs. Transitions:

• Add a new song not yet used: dp[i][j] += dp[i-1][j-1] * (n - (j-1)) (n-(j-1) new songs available).
• Replay an old song (if j > k): dp[i][j] += dp[i-1][j] * max(0, j - k) (j-k songs eligible for replay). Base: dp[0][0] = 1. Answer: dp[goal][n].

Example explanation

n=3, goal=3, k=1. Three songs played once each in any order.

• dp[1][1] = 1*3 = 3 (pick any of 3 songs first).
• dp[2][2] = dp[1][1]*2 + dp[1][2]max(0,2-1) = 32+0=6.
• dp[3][3] = dp[2][2]*(3-2) + dp[2][3]max(0,3-1) = 61+0=6. Answer = 6.

Common mistakes candidates make

• Off-by-one in the "eligible songs for replay" formula: must be j - k, not j - k - 1.
• Confusing "exactly j songs" with "at most j songs."
• Not applying modular arithmetic at each multiplication.
• Using 1-indexed dp without adjusting transition formulas.

Interview preparation tip

Music playlist DP is a variant of "count permutations with constraints." The key distinction: adding a new song vs replaying an old one are two separate transitions. Derive the formula by thinking: "If we have j songs in the playlist so far and add position i, either we introduce the j-th new song (from n-(j-1) options) or replay an eligible old song (from j-k options if j>k)." Practice similar counting DP problems with "at least once" and "cooldown" constraints to build intuition.