Number Of Music Playlists - Leetcode Solution

Problem Statement:

Your music player contains n different songs and she wants to listen to l (not necessarily different) songs during your trip. You create a playlist so that:

• Every song is played at least once
• A song can only be played again only if k other songs have been played

Return the number of possible playlists. As the answer can be very large, return it modulo 10^9 + 7.

Example input 1:

n = 3

l = 3

k = 1

Output: 6

Example input 2:

n = 2

l = 3

k = 0

Output: 0

Solution:

Approach:

First, we should realize that the order of the songs in the playlist does matter. For example, if we have 3 songs A, B, and C and the rules require that every song is played at least once, then the playlist ABAC is different from ABCA, even though they contain the same songs.

The second realization is that it’s easier to calculate the number of playlists that don’t satisfy the second rule than the ones that do.

Thus, we start by calculating the number of invalid playlists. A playlist is invalid if one or more of the n songs are not present, or a song is repeated before k other songs are played.

Let dp[i][j] be the number of playlists of length i that contain exactly j unique songs. We can calculate dp[i][j] based on all previous dp entries (using the previously derived formulas). For dp[i][j] with j>0, we need to add dp[i-1][j-1] * (n-j+1) to dp[i][j] to account for the case where we add a new song.

To calculate the number of playlists that don’t satisfy the second rule, we add up all dp[l][j] where j<n.

Finally, we subtract the invalid playlists from the total number of possible playlists. The total number of possible playlists is n! (as every unique song can appear in any place), so the time complexity of this algorithm is O(n*l). However, we need to take care of overflow in the calculations. Thus, we use a dynamic programming solution that uses a 2D array to store the intermediate results.

Algorithm:

1. Initialize an n x l 2-D array dp with zeroes.

2. Set dp[0][0] to 1, since if the playlist hasn’t started yet, there’s only one way to achieve the empty playlist.

3. For i=1 to l and j=1 to n:

   a. For dp[i][j], add the value of dp[i-1][j-1] * (n-j+1) to the total. This means that we add a new unique song in the playlist.

   b. For dp[i][j], add the value of dp[i-1][j] * max(0, j-k) to the total. This means that we repeat a song whose last play occurred at least k steps ago.

   c. Ensure that dp[i][j] is less than 10^9+7.

4. Initialize invalid to 0.

5. For j=0 to n:

   a. Add dp[l][j] to invalid.

6. Compute total as n!.

7. Subtract invalid from total, taking care of overflow.

8. Return the solution.

Python Code:

def numMusicPlaylists(self, n: int, l: int, k: int) -> int:

    dp = [[0 for _ in range(n+1)] for _ in range(l+1)] 
    dp[0][0] = 1
    
    MOD = 10**9+7
    
    for i in range(1, l+1):
        for j in range(1, n+1):
            dp[i][j] += dp[i-1][j-1] * (n-j+1)
            dp[i][j] += dp[i-1][j] * max(0, j-k)
            dp[i][j] %= MOD
    
    invalid = 0
    for j in range(n):
        invalid += dp[l][j]
    
    total = 1
    for i in range(1, n+1):
        total = (total*i) % MOD
    
    return (total - invalid) % MOD

Time complexity: O(n*l).

Space complexity: O(n*l).

1