# LeetCode 920: Number of Music Playlists

## Problem Restatement

We have `n` different songs.

We need to create a playlist of length `goal`.

The playlist must satisfy two rules:

| Rule | Meaning |
|---|---|
| Use every song | Each of the `n` songs must appear at least once |
| Replay restriction | A song can be replayed only after at least `k` other songs have been played |

Return the number of valid playlists modulo:

```python
10**9 + 7
```

The official problem asks for the number of possible playlists given `n`, `goal`, and `k`.

## Input and Output

| Item | Meaning |
|---|---|
| Input | Integers `n`, `goal`, and `k` |
| Output | Number of valid playlists |
| Required | Every song must appear at least once |
| Restriction | A repeated song needs at least `k` different songs before it |
| Modulo | `10^9 + 7` |

Function shape:

```python
def numMusicPlaylists(n: int, goal: int, k: int) -> int:
    ...
```

## Examples

Example 1:

```python
n = 3
goal = 3
k = 1
```

We need a playlist of length `3` using all `3` songs.

Since the playlist length equals the number of songs, each song appears exactly once.

Valid playlists:

```python
[1, 2, 3]
[1, 3, 2]
[2, 1, 3]
[2, 3, 1]
[3, 1, 2]
[3, 2, 1]
```

Answer:

```python
6
```

Example 2:

```python
n = 2
goal = 3
k = 0
```

Both songs must appear at least once.

Since `k = 0`, a song can repeat immediately.

Valid playlists:

```python
[1, 1, 2]
[1, 2, 1]
[2, 1, 2]
[2, 2, 1]
```

Answer:

```python
4
```

Example 3:

```python
n = 2
goal = 3
k = 1
```

A song cannot repeat until at least one other song has played.

Valid playlists:

```python
[1, 2, 1]
[2, 1, 2]
```

Answer:

```python
2
```

## First Thought: Generate Every Playlist

A direct method is to generate every possible playlist of length `goal`.

Each position has `n` choices, so there are:

```python
n ** goal
```

possible playlists.

For each playlist, we could check:

1. Whether every song appears.
2. Whether every repeated song respects the `k` rule.

This is too slow.

We need to count valid playlists without enumerating them.

## Key Insight

Build the playlist one position at a time.

At any point, we only need to know:

1. The current playlist length.
2. How many distinct songs have already been used.

Let:

```python
dp[i][j]
```

mean:

The number of playlists of length `i` that use exactly `j` distinct songs.

There are two ways to extend such a playlist.

## Transition 1: Add a New Song

If the playlist currently uses `j - 1` distinct songs, then we can add a new song as the next song.

There are:

```python
n - (j - 1)
```

unused songs available.

So:

```python
dp[i][j] += dp[i - 1][j - 1] * (n - j + 1)
```

## Transition 2: Replay an Old Song

If the playlist already uses `j` distinct songs, we may replay one of them.

But the last `k` different songs are blocked from replay.

So the number of replayable songs is:

```python
j - k
```

if `j > k`.

Thus:

```python
dp[i][j] += dp[i - 1][j] * (j - k)
```

This is the standard DP recurrence for this problem.

## Algorithm

1. Create a DP table with `(goal + 1)` rows and `(n + 1)` columns.
2. Set:

```python
dp[0][0] = 1
```

There is one way to create an empty playlist with zero songs used.

3. For each playlist length `i` from `1` to `goal`:
   - For each distinct song count `j` from `1` to `n`:
     - Add ways that place a new song.
     - Add ways that replay an old allowed song.
4. Return:

```python
dp[goal][n]
```

because the final playlist must have length `goal` and use all `n` songs.

## Correctness

The DP state `dp[i][j]` counts playlists of length `i` that use exactly `j` distinct songs.

Every valid playlist of length `i` with `j` distinct songs ends in exactly one of two ways.

The last song is new. Then the first `i - 1` songs used exactly `j - 1` distinct songs, and there are `n - j + 1` choices for the new song.

Or the last song was already used before. Then the first `i - 1` songs already used exactly `j` distinct songs, and only `j - k` of those songs are legal to replay because the most recent `k` different songs are blocked.

These two cases are disjoint and cover all possible valid endings.

The recurrence therefore counts every valid playlist exactly once.

The base case `dp[0][0] = 1` is correct because there is exactly one empty playlist.

At the end, `dp[goal][n]` counts playlists of the required length that use all songs at least once.

Therefore, the algorithm returns the required number.

## Complexity

| Metric | Value | Why |
|---|---:|---|
| Time | `O(goal * n)` | We fill one DP state for each length and distinct-song count |
| Space | `O(goal * n)` | The full DP table is stored |

## Implementation

```python
class Solution:
    def numMusicPlaylists(self, n: int, goal: int, k: int) -> int:
        MOD = 10**9 + 7

        dp = [[0] * (n + 1) for _ in range(goal + 1)]
        dp[0][0] = 1

        for i in range(1, goal + 1):
            for j in range(1, n + 1):
                add_new = dp[i - 1][j - 1] * (n - j + 1)

                replay_old = 0
                if j > k:
                    replay_old = dp[i - 1][j] * (j - k)

                dp[i][j] = (add_new + replay_old) % MOD

        return dp[goal][n]
```

## Code Explanation

Create the modulo constant:

```python
MOD = 10**9 + 7
```

Create the DP table:

```python
dp = [[0] * (n + 1) for _ in range(goal + 1)]
```

The empty playlist base case is:

```python
dp[0][0] = 1
```

For each length and distinct-song count:

```python
for i in range(1, goal + 1):
    for j in range(1, n + 1):
```

Count ways to add a song that has never appeared before:

```python
add_new = dp[i - 1][j - 1] * (n - j + 1)
```

Count ways to replay an old song:

```python
if j > k:
    replay_old = dp[i - 1][j] * (j - k)
```

Combine both cases:

```python
dp[i][j] = (add_new + replay_old) % MOD
```

The answer must use all `n` songs:

```python
return dp[goal][n]
```

## Testing

```python
def run_tests():
    s = Solution()

    assert s.numMusicPlaylists(3, 3, 1) == 6
    assert s.numMusicPlaylists(2, 3, 0) == 4
    assert s.numMusicPlaylists(2, 3, 1) == 2
    assert s.numMusicPlaylists(1, 1, 0) == 1
    assert s.numMusicPlaylists(3, 4, 1) == 18
    assert s.numMusicPlaylists(3, 5, 2) == 6

    print("all tests passed")

run_tests()
```

Test meaning:

| Test | Why |
|---|---|
| `n = 3, goal = 3, k = 1` | All songs appear exactly once |
| `n = 2, goal = 3, k = 0` | Immediate replay allowed |
| `n = 2, goal = 3, k = 1` | Alternating songs only |
| `n = 1, goal = 1, k = 0` | Minimum valid case |
| `n = 3, goal = 4, k = 1` | Requires one legal replay |
| `n = 3, goal = 5, k = 2` | Strong replay restriction |