Solution


Approach 1: Dynamic Programming

Intuition

Let dp[i][j] be the number of playlists of length i that have exactly j unique songs. We want dp[L][N], and it seems likely we can develop a recurrence for dp.

Algorithm

Consider dp[i][j]. Last song, we either played a song for the first time or we didn't. If we did, then we had dp[i-1][j-1] * (N-j) ways to choose it. If we didn't, then we repeated a previous song in dp[i-1][j] * max(j-K, 0) ways (j of them, except the last K ones played are banned.)

Complexity Analysis

  • Time Complexity: .

  • Space Complexity: . (However, we can adapt this algorithm to only store the last row of dp to easily get space complexity.)


Approach 2: Partitions + Dynamic Programming

(Note: This solution is extremely challenging, but is a natural consequence of trying to enumerate the playlists in this manner.)

Intuition

Since we are interested in playing every song at least once, let's keep track of what times a song was played that wasn't yet played before. For example, if we have 5 songs abcde, and we play abacabdcbaeacbd, then as these are the first occurrences of a unique song. For convenience, we'll also put . Our strategy is to count the number of playlists that satisfy this , so that our final answer will be .

Doing a direct count,

Now, let , so that . To recap, the final answer will be (for ):

For convenience, let's denote the stuff in the large brackets as .

Algorithm

We can develop a recurrence for mathematically, by factoring out the term.

so that it can be shown through algebraic manipulation that:

With this recurrence, we can perform dynamic programming similar to Approach 1. The final answer is .

Complexity Analysis

  • Time Complexity: .

  • Space Complexity: .


Approach 3: Generating Functions

(Note: This solution is extremely challenging and not recommended for interviews, but is included here for completeness.)

Analysis

Following the terminology of Approach 2, we would like to compute quickly. We can use generating functions.

For a fixed , consider the function:

The coefficient of in (denoted ) is the desired .

By the Chinese Remainder theorem on polynomials, this product can be written as a partial fraction decomposition:

for some rational coefficients . We can solve for these coefficients by clearing denominators and setting for . Then for a given , all the terms except the -th vanish, and:

Since a geometric series has sum , altogether it implies:

so that the final answer is

We only need a quick way to compute . Indeed,

so that we now have everything we need to compute the answer quickly.

Complexity Analysis

  • Time Complexity: .

  • Space Complexity: .


Analysis written by: @awice.