Practice/Google/Leetcode 920. Number of Music Playlists

Leetcode 920. Number of Music Playlists

CodingMust

Problem

You are building a music streaming application that needs to generate concert playlists. A valid playlist must satisfy these rules:

• The playlist contains exactly goal songs
• You have a library of n distinct songs to choose from
• Every one of the n songs must appear in the playlist at least once
• Once a song is played, it cannot be played again until at least k other distinct songs have been played

Your task is to count how many different valid playlists can be created following these rules.

Since the answer can be very large, return it modulo 10^9 + 7.

Requirements

1. Create a playlist of exactly goal songs
2. Use all n distinct songs at least once
3. Enforce a cooldown: a song can only be replayed after k different songs have been played
4. Return the count modulo 10^9 + 7

Constraints

• 1 <= k < n <= goal <= 100
• The answer fits in a 64-bit signed integer before taking the modulo

Examples

Example 1:

Input: n = 3, goal = 3, k = 1 Output: 6 Explanation: With 3 songs \{A, B, C\} and a playlist of length 3, every song appears exactly once. Since k=1, we cannot replay immediately. This is simply all permutations: ABC, ACB, BAC, BCA, CAB, CBA = 6 playlists.

Example 2:

Input: n = 2, goal = 3, k = 0 Output: 6 Explanation: With songs \{A, B\} and playlist length 3, we need to use both songs but one will repeat. Since k=0, songs can be played consecutively. Valid playlists: AAB, ABA, ABB, BAA, BAB, BBA = 6 playlists.

Example 3:

Input: n = 2, goal = 3, k = 1 Output: 2 Explanation: With k=1, we must play a different song before replaying. Valid patterns: ABA, BAB = 2 playlists.