Longest Diverse Sub-Playlist
Spotify is always looking for ways to enhance user experience by recommending diverse content. One aspect of diversity in playlists is the variety of genres. For a given playlist, we want to identify the longest continuous segment (sub-playlist) that features a specific number of unique genres.
This problem challenges your ability to efficiently analyze sequential data, a common task in music streaming platforms, using fundamental data structures and algorithms.
Implement a function longestDiverseSubPlaylist that takes an array of genre IDs (integers) representing a playlist and an integer k, and returns the length of the longest continuous sub-playlist that contains exactly k distinct genre IDs.
Input:
songGenres: An array of integers, where each integer songGenres[i] represents a genre ID of the i-th song in the playlist.k: An integer representing the target number of distinct genre IDs.Output:
k distinct genre IDs. If no such sub-playlist exists, return 0.k is 0, an empty sub-playlist has 0 distinct genres. However, the problem asks for the length of the longest such sub-playlist. If k=0, and songGenres is non-empty, no non-empty sub-playlist will have 0 distinct genres. Thus, the longest sub-playlist with 0 distinct genres would be an empty one, returning 0.Examples
Example 1
Input:
songGenres = [1,2,1,3,2,4], k = 3
Output:
5
Note:
The sub-playlist [1,2,1,3,2] has genres {1, 2, 3}, which are 3 distinct genres. Its length is 5. Other sub-playlists like [1,2,1,3] (length 4) or [3,2,4] (length 3) also have 3 distinct genres, but 5 is the maximum length.
Example 2
Input:
songGenres = [5,5,5,5,5], k = 1
Output:
5
Note:
The entire playlist [5,5,5,5,5] has only 1 distinct genre (genre 5). Its length is 5, which is the maximum possible.
Example 3
Input:
songGenres = [1,2,3,4,5], k = 2
Output:
2
Note:
Several sub-playlists have exactly 2 distinct genres, e.g., [1,2], [2,3], [3,4], [4,5]. Each has length 2. This is the maximum.
Example 4
Input:
songGenres = [1,2,1,3,2,4], k = 0
Output:
0
Note:
A sub-playlist with 0 distinct genres must be empty. The length of an empty sub-playlist is 0.
Example 5
Input:
songGenres = [1,1,2,2], k = 3
Output:
0
Note:
The entire playlist only has 2 distinct genres (1 and 2). It's impossible to form a sub-playlist with exactly 3 distinct genres. So, the result is 0.
Constraints
1 <= songGenres.length <= 10^51 <= songGenres[i] <= 10^90 <= k <= songGenres.lengthsongGenres not an array, k not an integer).k=0, k being larger than total distinct genres, or songGenres containing only one distinct genre?Loading editor...