Number of Music Playlists - Video Solutions

Problem Overview: You need to count how many playlists of length goal can be created using n unique songs where every song appears at least once and a song can only repeat after k other songs have played. The result must be returned modulo 1e9 + 7. The challenge is enforcing both constraints: using all songs and respecting the repeat gap.

Approach 1: Dynamic Programming with State Definition (O(n × goal) time, O(n × goal) space)

Define dp[i][j] as the number of playlists of length i that contain exactly j unique songs. Two choices exist when building the playlist. First, add a new song that hasn't appeared yet. There are n - (j - 1) options, so transition from dp[i-1][j-1]. Second, replay an existing song, but only those not used in the last k positions. That leaves max(j - k, 0) valid songs, transitioning from dp[i-1][j]. Iterate i from 1 to goal and j from 1 to n. This bottom‑up dynamic programming formulation cleanly enforces both constraints and is the standard interview solution.

Approach 2: Top-Down Dynamic Programming with Memoization (O(n × goal) time, O(n × goal) space)

The same recurrence can be implemented recursively with memoization. Define a function dfs(i, j) representing playlists of length i using j unique songs. Recursively compute the two transitions: add a new song (n - j choices) or reuse an old song (max(j - k, 0) choices). Cache results in a memo table to avoid recomputation. This top‑down style is often easier to reason about because the recurrence mirrors the problem definition directly. The technique combines dynamic programming with recursion and works well when you want clear state transitions without manually filling a table.

Combinatorics Insight: The DP works because it separates the problem into counting playlists by how many unique songs have been introduced so far. Each step either introduces a new element from the remaining pool or reuses an eligible one that satisfies the k-distance rule. This perspective connects the problem to counting permutations with constraints, a common theme in combinatorics and math-driven DP problems.

Recommended for interviews: The bottom‑up DP with state dp[i][j] is what most interviewers expect. It demonstrates you can design states, derive transitions, and enforce constraints mathematically. Mentioning the recursive memoized version shows strong understanding of the recurrence and flexibility in implementation.