Longest Playlist With No Repeated Songs : Brute Force to Optimal

You are given a user's listening history, where songs are stored in the order they were played:

Song1, Song2, Song3, Song1, Song4, Song2

Your task is to find the longest possible playlist that can be created from this listening history. The playlist must follow these rules:

1. The songs must remain in the same order as the user's listening history.
2. The playlist must contain a continuous sequence of songs. You cannot skip any song.
3. No song can be repeated within the playlist.
4. Return the length of the longest valid playlist.

For the example above, the answer is 4, one such playlist is Song2, Song3, Song1, Song4.

Understanding the Problem First

Before jumping into code, let's pin down exactly what we're being asked for, because two words in the problem statement do all the heavy lifting:

• "Continuous sequence" → we are looking at a window of the array. Once we pick a starting song, every song after it up to some ending song must be included we can't cherry-pick.
• "No song repeated" → within that window, every song must be unique.

So really, we're searching over all possible windows [i, j] of the history array and among all windows where every element is unique, we want the one with the maximum length j - i + 1.

That framing naturally gives us a spectrum of solutions from "try every window and check it" (slow but obviously correct) to "smartly grow and shrink one window as we scan" (fast). Let's walk through that spectrum step by step.

Approach 1: Brute Force (Check Every Window)

The most direct translation of the problem into code: generate every possible contiguous window [i, j] and for each one, check whether all songs in it are distinct. Keep track of the largest window length where the check passes. To check "are all songs in this window distinct?", we can insert each song into a HashSet as we go if an insertion fails (song already present), the window is invalid.

Dry Run

For [Song1, Song2, Song3, Song1, Song4, Song2]:

• Start i = 0: extend j from 0 → 1 → 2 (all unique, length 3), then j = 3 hits Song1 again → stop this window at length 3.
• Start i = 1: extend j from 1 → 2 → 3 → 4 (all unique, length 4), then j = 5 hits Song2 again → stop at length 4.
• Start i = 2: extend similarly...
• ...continue for every i.

We track the maximum length seen across all starting points. This is a straightforward "brute force" because we're not reusing any work between different values of i every window starts its uniqueness check from scratch.

// Java Code
import java.util.HashSet;
import java.util.Set;

public class PlaylistBruteForce {

    public static int longestPlaylist(String[] history) {
        int n = history.length;
        int maxLength = 0;
        // Try every possible starting index
        for (int i = 0; i < n; i++) {
            Set<String> seen = new HashSet<>();
            // Extend the window as far right as possible
            for (int j = i; j < n; j++) {
                if (seen.contains(history[j])) {
                    // Repeated song found, this window can't extend further
                    break;
                }
                seen.add(history[j]);
                maxLength = Math.max(maxLength, j - i + 1);
            }
        }
        return maxLength;
    }
    public static void main(String[] args) {
        String[] history = {"Song1", "Song2", "Song3", "Song1", "Song4", "Song2"};
        System.out.println("Longest Playlist Length: " + longestPlaylist(history));
        // Output: 4
    }
}

Why It Works

For every starting point i, we greedily extend j until we hit a duplicate and since the window is checked incrementally (not re-verified from scratch with nested loops), this is already a slight improvement over the "textbook" brute force that would use three nested loops (pick i, pick j, then loop again to verify uniqueness).

Complexity

This works fine for small histories, but if a user has 100,000 plays in their history, n² becomes 10 billion operations far too slow.

Approach 2: Sliding Window with HashSet

The brute force approach wastes work: for every starting index i, it throws away everything it learned at the previous starting index, rebuilds the HashSet from scratch and re-scans forward even though most of that scanning repeats work already done.

Instead of restarting for every i, we can maintain a single window and let it evolve incrementally, driven by the right pointer moving forward one step at a time. This is the classic sliding window technique:

• Maintain two pointers, left and right, marking the current window.
• Maintain a HashSet of songs currently inside the window.
• Move right forward one step at a time, trying to add history[right] to the set.
• If history[right] is not already in the set, adding it can't create a duplicate the window simply grows and it stays valid.
• If history[right] is already in the set, adding it would create a duplicate. So before adding it, keep removing the song at left (and moving left forward) until the duplicate is cleared. Removing an element can never create a new duplicate, it can only eliminate one, so once the offending song is gone, the window is guaranteed valid again.
• After every step, update the maximum window length.

The key insight: both pointers only move forward and left only moves in reaction to a duplicate appearing at right we never rebuild the set from scratch for a new starting point. That's what makes this fast.

Dry Run

[Song1, Song2, Song3, Song1, Song4, Song2], indices 0..5

Maximum length observed: 4

// Java Code
import java.util.HashSet;
import java.util.Set;

public class PlaylistSlidingWindowSet {

    public static int longestPlaylist(String[] history) {
        int n = history.length;
        Set<String> window = new HashSet<>();
        int left = 0;
        int maxLength = 0;
        for (int right = 0; right < n; right++) {
            // Shrink from the left until the duplicate is gone
            while (window.contains(history[right])) {
                window.remove(history[left]);
                left++;
            }
            // Now it's safe to add the current song
            window.add(history[right]);
            // Update the max window length seen so far
            maxLength = Math.max(maxLength, right - left + 1);
        }
        return maxLength;
    }
    public static void main(String[] args) {
        String[] history = {"Song1", "Song2", "Song3", "Song1", "Song4", "Song2"};
        System.out.println("Longest Playlist Length: " + longestPlaylist(history));
        // Output: 4
    }
}

Extension: Printing the Actual Playlist

The length tells us how long the answer is, but not which songs make it up. To recover the songs themselves, we track the left pointer's value at the exact moment a new maximum length is found (call it bestStart) and once the scan finishes, slice the array from bestStart to bestStart + maxLength.

import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;

public class PlaylistSlidingWindowSetWithPrint {

    public static int longestPlaylist(String[] history, int[] result) {
        int n = history.length;
        Set<String> window = new HashSet<>();
        int left = 0;
        int maxLength = 0;
        int bestStart = 0; // start index of the best window found so far
        for (int right = 0; right < n; right++) {
            // Shrink from the left until the duplicate is gone
            while (window.contains(history[right])) {
                window.remove(history[left]);
                left++;
            }
            // Now it's safe to add the current song
            window.add(history[right]);
            // Update the max window length and remember where it started
            int currentLength = right - left + 1;
            if (currentLength > maxLength) {
                maxLength = currentLength;
                bestStart = left;
            }
        }
        result[0] = bestStart; // pass the start index back to the caller
        return maxLength;
    }

    public static void main(String[] args) {
        String[] history = {"Song1", "Song2", "Song3", "Song1", "Song4", "Song2"};
        int[] bestStartHolder = new int[1];
        int length = longestPlaylist(history, bestStartHolder);
        String[] playlist = Arrays.copyOfRange(history, bestStartHolder[0], bestStartHolder[0] + length);
        System.out.println("Longest Playlist Length: " + length);
        System.out.println(String.join(", ", playlist) + " → length " + length);
        // Output:
        // Longest Playlist Length: 4
        // Song2, Song3, Song1, Song4 → length 4
    }
}

Why It Works

Each song is added to the HashSet at most once and removed at most once as right and left sweep across the array. Since both pointers move strictly forward and never revisit a position, the total number of add/remove operations is bounded by 2n, not n².

Complexity

Approach 3: Sliding Window with HashMap

Approach 2 is already O(n), but look closely at the inner while loop when we hit a duplicate, we remove songs from the left one at a time until the duplicate clears. In the worst case (e.g., the same song repeating at the very start and very end of a long, otherwise-unique stretch), this can still mean a lot of individual removal steps.

We can do better by directly jumping left to the position right after the previous occurrence of the duplicate song, instead of inching forward one element at a time. To do this, we store not just whether we've seen a song, but the last index where we saw it which calls for a HashMap<String, Integer> instead of a HashSet.

Steps:

• Maintain a HashMap mapping each song to the most recent index it was played at.
• For each song at index right:
  • If the song was seen before and that previous occurrence is inside the current window (i.e., lastSeenIndex >= left), jump left to lastSeenIndex + 1.
  • Update the song's last-seen index to right.
  • Update the max window length.

This guarantees left only ever moves forward and each index is processed in strictly O(1) amortized work no inner while loop needed at all.

Dry Run

[Song1, Song2, Song3, Song1, Song4, Song2]

Maximum length observed: 4

Notice how at right = 3, instead of removing songs one at a time from the HashSet, we directly compute left = lastSeenIndex + 1 = 1 in a single step.

// Java Code
import java.util.HashMap;
import java.util.Map;

public class PlaylistSlidingWindowMap {

    public static int longestPlaylist(String[] history) {
        int n = history.length;
        Map<String, Integer> lastSeenIndex = new HashMap<>();
        int left = 0;
        int maxLength = 0;
        for (int right = 0; right < n; right++) {
            String currentSong = history[right];
            // If this song was seen before AND that occurrence is
            // still inside our current window, jump left past it
            if (lastSeenIndex.containsKey(currentSong)
                    && lastSeenIndex.get(currentSong) >= left) {
                left = lastSeenIndex.get(currentSong) + 1;
            }
            // Record/update the most recent index for this song
            lastSeenIndex.put(currentSong, right);
            // Update the max window length
            maxLength = Math.max(maxLength, right - left + 1);
        }
        return maxLength;
    }

    public static void main(String[] args) {
        String[] history = {"Song1", "Song2", "Song3", "Song1", "Song4", "Song2"};
        System.out.println("Longest Playlist Length: " + longestPlaylist(history));
        // Output: 4
    }
}

Extension: Printing the Actual Playlist

Same idea as before: track bestStart (the left pointer's value at the moment a new max length is found) alongside maxLength, then slice the array once the single pass finishes. No extra loop or second pass is needed this stays true to the O(n) optimal approach.

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

public class PlaylistSlidingWindowMapWithPrint {

    public static int longestPlaylist(String[] history, int[] result) {
        int n = history.length;
        Map<String, Integer> lastSeenIndex = new HashMap<>();
        int left = 0;
        int maxLength = 0;
        int bestStart = 0; // start index of the best window found so far
        for (int right = 0; right < n; right++) {
            String currentSong = history[right];
            // If this song was seen before AND that occurrence is
            // still inside our current window, jump left past it
            if (lastSeenIndex.containsKey(currentSong)
                    && lastSeenIndex.get(currentSong) >= left) {
                left = lastSeenIndex.get(currentSong) + 1;
            }
            // Record/update the most recent index for this song
            lastSeenIndex.put(currentSong, right);
            // Update the max window length and remember where it started
            int currentLength = right - left + 1;
            if (currentLength > maxLength) {
                maxLength = currentLength;
                bestStart = left;
            }
        }
        result[0] = bestStart; // pass the start index back to the caller
        return maxLength;
    }

    public static void main(String[] args) {
        String[] history = {"Song1", "Song2", "Song3", "Song1", "Song4", "Song2"};
        int[] bestStartHolder = new int[1];
        int length = longestPlaylist(history, bestStartHolder);
        String[] playlist = Arrays.copyOfRange(history, bestStartHolder[0], bestStartHolder[0] + length);
        System.out.println("Longest Playlist Length: " + length);
        System.out.println(String.join(", ", playlist) + " → length " + length);
        // Output:
        // Longest Playlist Length: 4
        // Song2, Song3, Song1, Song4 → length 4
    }
}

Note: since multiple windows can tie for the maximum length (as we saw earlier both Song2, Song3, Song1, Song4 and Song3, Song1, Song4, Song2 have length 4), this code prints the first such window encountered while scanning left to right, since bestStart only updates on a strict > comparison. Changing that condition to >= would instead print the last one.

Why This Is the Optimal Approach

• Every index right is visited exactly once.
• left only ever moves forward and it moves in a single O(1) jump rather than a sequence of removals.
• There's no nested loop of any kind this is a true single-pass O(n) algorithm.

This is the same core pattern used to solve the well-known "Longest Substring Without Repeating Characters" problem a very common interview question so recognizing this pattern is valuable well beyond just this playlist scenario.

Complexity

Comparing All Approaches

While both sliding window approaches are O(n) asymptotically, the HashMap version does strictly less work in practice since it eliminates the inner while loop entirely every operation is O(1) with no amortization argument needed.

Key Takeaways

1. Recognize the window pattern early. Any time a problem asks for the longest/shortest contiguous segment satisfying some condition, sliding window should be one of the first techniques you consider.
2. Brute force is a stepping stone, not a dead end. Writing the O(n²) version first helps you see why the sliding window works the optimal solution literally comes from asking "what work am I repeating unnecessarily?"
3. HashSet vs. HashMap is about what you need to remember. A HashSet only tells you if something exists in the window. A HashMap tells you where it last existed and that extra bit of information is what lets you jump instead of crawl.
4. This pattern generalizes. The exact same technique solves "longest substring without repeating characters", "longest subarray with at most K distinct elements," and several other frequently-asked interview problems.