DSAPROB30 - Editorial

editorial
, ,
1

Problem Link - Unique Songs

Problem Statement:

The chef is hosting a party where he’s a DJ, setting up a new playlist for the party. He has a list of songs, each with a unique ID. Help him find the longest consecutive songs where no song repeats.

Approach:

The key idea of this problem is to use a sliding window technique with a set to keep track of the unique songs in the current subsequence. The window expands by adding songs one by one to the playlist and contracts when a repeated song is encountered. The goal is to keep track of the longest sequence of unique songs during this process.

Here’s how it works step-by-step:

  1. Sliding Window:

    • Use two pointers: one to represent the start of the window (start) and the other for the end, which moves through the list of songs.
    • For each song at position end, check if it is already in the current sequence (tracked by a set currentSongs).

  2. Handling Duplicates:

    • If the current song at end is already in the set (meaning it’s a repeat), we start removing songs from the start of the window until the duplicate is no longer in the sequence.

  3. Update Maximum Length:

    • After adjusting the window, we compute the length of the current unique sequence (end - start + 1) and update the maximum length (maxLength) if this sequence is longer than the previous longest.

Time Complexity:

  • The time complexity of this approach is O(n), where n is the number of songs. This is because each song is added and removed from the set at most once, and the set operations (insert, delete, find) all take constant time on average.

Space Complexity:

  • The space complexity is O(n), as we are using a set to store the unique songs in the current sequence.