Longest Playlist With No Repeated Songs : Brute Force to Optimal

DevSniper

Last Updated : 25 August 2026

27 Views

#greedy

Adℹ

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:

The songs must remain in the same order as the user's listening history.
The playlist must contain a continuous sequence of songs. You cannot skip any song.
No song can be repeated within the playlist.
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

	Value
Time	O(n²) for each of the `n` starting indices, we may scan up to `n` elements again
Space	O(min(n, k)) where `k` = number of distinct songs, for the `HashSet` used per starting index

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

right	song	action	window	length
0	Song1	add	[0,0]	1
1	Song2	add	[0,1]	2
2	Song3	add	[0,2]	3
3	Song1	duplicate! remove Song1 (left=0→1)	[1,3]	3
4	Song4	add	[1,4]	4
5	Song2	duplicate! remove Song2 (left=1→2)	[2,5]	4

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

	Value
Time	O(n) technically O(2n) since each element can be added and removed once, which simplifies to O(n)
Space	O(min(n, k)) for the `HashSet`, where `k` = number of distinct songs

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]

right	song	lastSeen before update	left before	left after	window length
0	Song1	none	0	0	1
1	Song2	none	0	0	2
2	Song3	none	0	0	3
3	Song1	index 0 (≥ left=0)	0	1	3
4	Song4	none	1	1	4
5	Song2	index 1 (< left=1? no, 1 ≥ 1)	1	2	4

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

	Value
Time	O(n) single pass, O(1) work per element
Space	O(min(n, k)) for the `HashMap`, where `k` = number of distinct songs

Comparing All Approaches

Approach	Time Complexity	Space Complexity	Core Idea
Brute Force	O(n²)	O(min(n, k))	Try every window starting point, extend until a duplicate appears
Sliding Window (HashSet)	O(n)	O(min(n, k))	Grow window right, shrink left one step at a time on duplicates
Sliding Window (HashMap)	O(n)	O(min(n, k))	Grow window right, jump left directly using last-seen index

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

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.
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?"
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.
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.

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

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

\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n

	Value
Time	O(n²) for each of the `n` starting indices, we may scan up to `n` elements again
Space	O(min(n, k)) where `k` = number of distinct songs, for the `HashSet` used per starting index

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

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.

Dry Run

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

\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n

right	song	action	window	length
0	Song1	add	[0,0]	1
1	Song2	add	[0,1]	2
2	Song3	add	[0,2]	3
3	Song1	duplicate! remove Song1 (left=0→1)	[1,3]	3
4	Song4	add	[1,4]	4
5	Song2	duplicate! remove Song2 (left=1→2)	[2,5]	4

Maximum length observed: 4

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

Extension: Printing the Actual Playlist

import java.util.Arrays;\nimport java.util.HashSet;\nimport java.util.Set;\n\npublic class PlaylistSlidingWindowSetWithPrint {\n\n    public static int longestPlaylist(String[] history, int[] result) {\n        int n = history.length;\n        Set<String> window = new HashSet<>();\n        int left = 0;\n        int maxLength = 0;\n        int bestStart = 0; // start index of the best window found so far\n        for (int right = 0; right < n; right++) {\n            // Shrink from the left until the duplicate is gone\n            while (window.contains(history[right])) {\n                window.remove(history[left]);\n                left++;\n            }\n            // Now it's safe to add the current song\n            window.add(history[right]);\n            // Update the max window length and remember where it started\n            int currentLength = right - left + 1;\n            if (currentLength > maxLength) {\n                maxLength = currentLength;\n                bestStart = left;\n            }\n        }\n        result[0] = bestStart; // pass the start index back to the caller\n        return maxLength;\n    }\n\n    public static void main(String[] args) {\n        String[] history = {\"Song1\", \"Song2\", \"Song3\", \"Song1\", \"Song4\", \"Song2\"};\n        int[] bestStartHolder = new int[1];\n        int length = longestPlaylist(history, bestStartHolder);\n        String[] playlist = Arrays.copyOfRange(history, bestStartHolder[0], bestStartHolder[0] + length);\n        System.out.println(\"Longest Playlist Length: \" + length);\n        System.out.println(String.join(\", \", playlist) + \" → length \" + length);\n        // Output:\n        // Longest Playlist Length: 4\n        // Song2, Song3, Song1, Song4 → length 4\n    }\n}\n

Why It Works

Complexity

\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n

	Value
Time	O(n) technically O(2n) since each element can be added and removed once, which simplifies to O(n)
Space	O(min(n, k)) for the `HashSet`, where `k` = number of distinct songs

Approach 3: Sliding Window with HashMap

Steps:

Maintain a HashMap mapping each song to the most recent index it was played at.
For each song at index right:\n
- 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.
\n

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]

\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n

right	song	lastSeen before update	left before	left after	window length
0	Song1	none	0	0	1
1	Song2	none	0	0	2
2	Song3	none	0	0	3
3	Song1	index 0 (≥ left=0)	0	1	3
4	Song4	none	1	1	4
5	Song2	index 1 (< left=1? no, 1 ≥ 1)	1	2	4

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\nimport java.util.HashMap;\nimport java.util.Map;\n\npublic class PlaylistSlidingWindowMap {\n\n    public static int longestPlaylist(String[] history) {\n        int n = history.length;\n        Map<String, Integer> lastSeenIndex = new HashMap<>();\n        int left = 0;\n        int maxLength = 0;\n        for (int right = 0; right < n; right++) {\n            String currentSong = history[right];\n            // If this song was seen before AND that occurrence is\n            // still inside our current window, jump left past it\n            if (lastSeenIndex.containsKey(currentSong)\n                    && lastSeenIndex.get(currentSong) >= left) {\n                left = lastSeenIndex.get(currentSong) + 1;\n            }\n            // Record/update the most recent index for this song\n            lastSeenIndex.put(currentSong, right);\n            // Update the max window length\n            maxLength = Math.max(maxLength, right - left + 1);\n        }\n        return maxLength;\n    }\n\n    public static void main(String[] args) {\n        String[] history = {\"Song1\", \"Song2\", \"Song3\", \"Song1\", \"Song4\", \"Song2\"};\n        System.out.println(\"Longest Playlist Length: \" + longestPlaylist(history));\n        // Output: 4\n    }\n}\n

Extension: Printing the Actual Playlist

import java.util.Arrays;\nimport java.util.HashMap;\nimport java.util.Map;\n\npublic class PlaylistSlidingWindowMapWithPrint {\n\n    public static int longestPlaylist(String[] history, int[] result) {\n        int n = history.length;\n        Map<String, Integer> lastSeenIndex = new HashMap<>();\n        int left = 0;\n        int maxLength = 0;\n        int bestStart = 0; // start index of the best window found so far\n        for (int right = 0; right < n; right++) {\n            String currentSong = history[right];\n            // If this song was seen before AND that occurrence is\n            // still inside our current window, jump left past it\n            if (lastSeenIndex.containsKey(currentSong)\n                    && lastSeenIndex.get(currentSong) >= left) {\n                left = lastSeenIndex.get(currentSong) + 1;\n            }\n            // Record/update the most recent index for this song\n            lastSeenIndex.put(currentSong, right);\n            // Update the max window length and remember where it started\n            int currentLength = right - left + 1;\n            if (currentLength > maxLength) {\n                maxLength = currentLength;\n                bestStart = left;\n            }\n        }\n        result[0] = bestStart; // pass the start index back to the caller\n        return maxLength;\n    }\n\n    public static void main(String[] args) {\n        String[] history = {\"Song1\", \"Song2\", \"Song3\", \"Song1\", \"Song4\", \"Song2\"};\n        int[] bestStartHolder = new int[1];\n        int length = longestPlaylist(history, bestStartHolder);\n        String[] playlist = Arrays.copyOfRange(history, bestStartHolder[0], bestStartHolder[0] + length);\n        System.out.println(\"Longest Playlist Length: \" + length);\n        System.out.println(String.join(\", \", playlist) + \" → length \" + length);\n        // Output:\n        // Longest Playlist Length: 4\n        // Song2, Song3, Song1, Song4 → length 4\n    }\n}\n

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

\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n

	Value
Time	O(n) single pass, O(1) work per element
Space	O(min(n, k)) for the `HashMap`, where `k` = number of distinct songs

Comparing All Approaches

\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n

Approach	Time Complexity	Space Complexity	Core Idea
Brute Force	O(n²)	O(min(n, k))	Try every window starting point, extend until a duplicate appears
Sliding Window (HashSet)	O(n)	O(min(n, k))	Grow window right, shrink left one step at a time on duplicates
Sliding Window (HashMap)	O(n)	O(min(n, k))	Grow window right, jump left directly using last-seen index

Key Takeaways

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.
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?\"
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.
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.

","categoryId":177,"subCategoryId":177,"contentFormat":5,"blogId":200,"userId":"MjlfNF84LVsyXTJuLXRDX0FOZ2VfX0l0","title":" Longest Playlist With No Repeated Songs : Brute Force to Optimal","url":"longest-playlist-with-no-repeated-songs-brute-force-to-optimal","bannerImage":"","seoDescription":"Find the longest playlist with no repeated songs using brute force, HashSet, and HashMap sliding window techniques, with Java code and dry runs.","generatedOn":"2026-08-25T10:33:35","updatedOn":"2026-08-25T10:33:35"},"popularContents":[{"id":34,"title":"System Design Deep Dive: 25 Essential Interview Questions","url":"system-design-deep-dive-25-essential-interview-questions","description":null,"seoDescription":"","contentType":5,"generatedOn":"2026-10-14T22:54:36.7728781Z","viewCount":0},{"id":173,"title":"Uber SDE-2 Interview Experience : LLD, HLD, DSA & Hiring Manager Round","url":"uber-sde-2-interview-experience-lld-hld-dsa-hiring-manager-round","description":null,"seoDescription":"Read a real Uber SDE-2 interview experience covering DSA, low-level design, high-level system design, behavioral rounds, hiring freeze and key takeaways.","contentType":5,"generatedOn":"2026-10-14T22:54:36.7728971Z","viewCount":0},{"id":130,"title":"Rippling SDE-2 Interview Experience (4+ Years Experience) | Offer Received | Coding, LLD & System Design","url":"rippling-sde-2-interview-experience-4-years-experience-offer-received-coding-lld-system-design","description":null,"seoDescription":"Detailed Rippling SDE-2 interview experience with complete 5 rounds, coding questions, rules engine design, system design and preparation tips.","contentType":5,"generatedOn":"2026-10-14T22:54:36.7728889Z","viewCount":0},{"id":163,"title":"Top 50 SQL Interview Questions and Answers (Beginner to Intermediate)","url":"top-sql-interview-questions-and-answers-beginner-to-intermediate","description":null,"seoDescription":"Top 50 SQL Interview Questions and Answers (Beginner to Intermediate). Top SQL Interview Questions for fresher. Frequently asked SQL interview questions with answers","contentType":2,"generatedOn":"2026-10-14T22:54:36.7705838Z","viewCount":0},{"id":118,"title":"JioHotstar Staff Software Engineer Interview Experience (Bangalore)","url":"jiohotstar-staff-software-engineer-interview-experience-bangalore","description":null,"seoDescription":"JioHotstar Staff Software Engineer interview experience covering Uber system design, API rate limiter LLD, leadership rounds, bar raiser and HR insights.","contentType":5,"generatedOn":"2026-10-14T22:54:36.7728824Z","viewCount":0},{"id":197,"title":"My Adobe SDE Interview Experience (Aug 2026) 5 Rounds, Selected","url":"my-adobe-sde-interview-experience-aug-2026-5-rounds-selected","description":null,"seoDescription":"Real Adobe SDE interview: 5 rounds, 4 DSA problems (Rotate Array, BSTs, Kth Smallest Matrix), code review & behavioral round. Full solutions + tips.","contentType":5,"generatedOn":"2026-10-14T22:54:36.7728985Z","viewCount":0},{"id":139,"title":"Blinkit (Eternal) SDE-1 Interview Experience (June 2026) – Offer Received","url":"blinkit-eternal-sde-1-interview-experience-june-2026-offer-received","description":null,"seoDescription":"Blinkit SDE-1 interview experience with a 30 LPA offer. Covers House Robber DP, ticket booking system design, culture fit round and tips.","contentType":5,"generatedOn":"2026-10-14T22:54:36.7728923Z","viewCount":0},{"id":167,"title":"Meesho SDE-1 Online Assessment Interview Experience (Remote) - Rejected","url":"meesho-sde-1-online-assessment-interview-experience-remote-rejected","description":null,"seoDescription":"Read a real Meesho SDE-1 online assessment experience with coding questions, DSA topics, solutions, difficulty level, preparation tips and interview insights.","contentType":5,"generatedOn":"2026-10-14T22:54:36.7728958Z","viewCount":0},{"id":135,"title":"Spinny SDE-1 Interview Experience (Selected)","url":"spinny-sde-1-interview-experience-selected","description":null,"seoDescription":"Spinny SDE-1 Interview Experience (Selected) | 4 Rounds Breakdown: Coding, LLD, Java, SQL + Real Interview Questions","contentType":5,"generatedOn":"2026-10-14T22:54:36.7728907Z","viewCount":0},{"id":153,"title":"Visa Software Engineer 1 (SDE-1) Interview Experience | CodeSignal OA + Graph-Based Technical Rounds","url":"visa-software-engineer-1-sde-1-interview-experience-codesignal-oa-graph-based-technical-rounds","description":null,"seoDescription":" Ace your Visa SDE-1 interview with this complete interview experience covering CodeSignal OA, graph coding rounds, hiring manager questions and tips.","contentType":5,"generatedOn":"2026-10-14T22:54:36.7728945Z","viewCount":0}],"latestContents":[{"id":219,"title":"6 Tools That Made My Life Easier as a Software Engineer","url":"6-tools-that-made-my-life-easier-as-a-software-engineer","description":null,"seoDescription":"The 6 developer tools I use daily as a software engineer: Git, VS Code, Docker, Postman, Chrome DevTools, and AI assistants, with real tips, mistakes, and trade","contentType":5,"generatedOn":"2026-10-14T22:54:36.7722723Z","viewCount":0},{"id":218,"title":"When Should a Business Use Multiple AI Agents Instead of One?","url":"when-should-a-business-use-multiple-ai-agents-instead-of-one","description":null,"seoDescription":"Single agent or multi-agent AI? Learn the 4 signals that justify splitting agents by knowledge, permissions, and risk, plus routing and handoff tips.","contentType":5,"generatedOn":"2026-10-14T22:54:36.7722762Z","viewCount":0},{"id":216,"title":"AI in Clinical Trials Market Estimated to Experience a Hike in Growth by 2035","url":"ai-in-clinical-trials-market-estimated-to-experience-a-hike-in-growth-by-2035","description":null,"seoDescription":"The exclusive information about market dynamics serves as a valuable guide to predict economic scenarios and initiatives taken to enhance future growth. Our mar","contentType":5,"generatedOn":"2026-10-14T22:54:36.7722773Z","viewCount":0},{"id":217,"title":"AI in Clinical Trials Market Estimated to Experience a Hike in Growth by 2035","url":"ai-in-clinical-trials-market-estimated-to-experience-a-hike-in-growth-by-2035","description":null,"seoDescription":"The exclusive information about market dynamics serves as a valuable guide to predict economic scenarios and initiatives taken to enhance future growth. Our mar","contentType":5,"generatedOn":"2026-10-14T22:54:36.7722784Z","viewCount":0},{"id":215,"title":"What Happens When an AI Agent Doesn't Know the Answer?","url":"what-happens-when-an-ai-agent-doesnt-know-the-answer","description":null,"seoDescription":"Most AI agents fail quietly. They guess instead of saying \"I don't know.\" Here's how to design better fallback and human-handoff behavior.","contentType":5,"generatedOn":"2026-10-14T22:54:36.7722792Z","viewCount":0},{"id":214,"title":"Greedy Algorithms Explained: How They Work, When They Fail and How to Use Them","url":"greedy-algorithms-explained-how-they-work-when-they-fail-and-how-to-use-them","description":null,"seoDescription":"Learn greedy algorithms step by step with C# code Dijkstra, Huffman coding, knapsack and MSTs plus when greedy fails and how to prove it's correct","contentType":5,"generatedOn":"2026-10-14T22:54:36.7722832Z","viewCount":0},{"id":213,"title":"Amazon SDE II Interview Experience (Bangalore, Selected) ~ Aug 2026","url":"amazon-sde-ii-interview-experience-bangalore-selected-aug-2026","description":null,"seoDescription":"Amazon SDE II interview experience from Bangalore covering 4 rounds, DSA, LLD, system design, Leadership Principles, coding questions and selection.","contentType":5,"generatedOn":"2026-10-14T22:54:36.7722841Z","viewCount":0},{"id":212,"title":"How to Get 10x Better AI Answers Without Writing Better Prompts : 10 Proven Techniques","url":"how-to-get-10x-better-ai-answers-without-writing-better-prompts-10-proven-techniques","description":null,"seoDescription":"Get better AI answers without complex prompts. Learn 10 practical techniques using context, examples, tools, feedback, and verification.","contentType":5,"generatedOn":"2026-10-14T22:54:36.772285Z","viewCount":0},{"id":211,"title":"I Interviewed for a Microsoft SDE I Role. Here's Everything That Happened.","url":"i-interviewed-for-a-microsoft-sde-i-role-heres-everything-that-happened","description":null,"seoDescription":"My real Microsoft SDE I interview experience, all 4 rounds, the exact DSA problems with fully tested solutions, the WhatsApp system design round","contentType":5,"generatedOn":"2026-10-14T22:54:36.7722859Z","viewCount":0},{"id":140,"title":"PolicyBazaar Software Development Engineer (SDE) Interview Experience | DSA, Core CS & System Design","url":"policybazaar-software-development-engineer-sde-interview-experience-dsa-core-cs-system-design","description":null,"seoDescription":"Detailed PolicyBazaar SDE interview experience covering 3 rounds: DSA coding, core CS assessment and system design with key learnings and insights.","contentType":5,"generatedOn":"2026-10-14T22:54:36.7722868Z","viewCount":0}],"relatedContents":[{"id":207,"title":"How to Find the Right View of a Binary Tree","url":"right-view-of-a-binary-tree","description":null,"seoDescription":"Learn how to find the right view of a binary tree using DFS and BFS, with examples, code, complexity analysis and coding interview tips.","contentType":5,"generatedOn":"2026-10-14T22:54:36.7759467Z","viewCount":0},{"id":206,"title":"Left View of a Binary Tree: DFS and BFS Approaches Explained","url":"left-view-of-a-binary-tree","description":null,"seoDescription":"Learn how to find the left view of a binary tree using DFS and BFS, with examples, code, complexity analysis, common mistakes and interview tips.","contentType":5,"generatedOn":"2026-10-14T22:54:36.7759504Z","viewCount":0},{"id":205,"title":"Top View of a Binary Tree Using BFS and DFS | Complete Guide","url":"top-view-of-a-binary-tree","description":null,"seoDescription":"Learn how to find the top view of a binary tree using DFS and BFS with step-by-step explanations, examples, code, complexity analysis and interview insights.","contentType":5,"generatedOn":"2026-10-14T22:54:36.7785117Z","viewCount":0},{"id":201,"title":"Bottom View of a Binary Tree: DFS vs BFS Approach","url":"bottom-view-of-a-binary-tree-dfs-vs-bfs-approach","description":null,"seoDescription":"Learn to find the bottom view of a binary tree using horizontal distance. Compares a buggy DFS attempt, a fixed DFS and the optimal BFS solution in Java.","contentType":5,"generatedOn":"2026-10-14T22:54:36.7785148Z","viewCount":0},{"id":90,"title":"Contain Virus : Deep, Intuitive & Fully Explained Guide","url":"contain-virus-deep-intuitive-fully-explained-guide","description":null,"seoDescription":"Contain Virus problem explained with DFS + greedy approach, step-by-step simulation, examples and optimized solutions for coding interviews.","contentType":5,"generatedOn":"2026-10-14T22:54:36.7785187Z","viewCount":0},{"id":37,"title":"Find the repeating and missing numbers","url":"find-the-repeating-and-missing-numbers","description":null,"seoDescription":"Find the repeating and missing numbers in an array from 1..n using brute force, hashmap, math and XOR, step-by-step explained with real-world use cases.","contentType":5,"generatedOn":"2026-10-14T22:54:36.7785201Z","viewCount":0},{"id":27,"title":"4 Sum | Find Quads that add up to a target value","url":"4-sum-find-quads-that-add-up-to-a-target-value","description":null,"seoDescription":"","contentType":5,"generatedOn":"2026-10-14T22:54:36.7785215Z","viewCount":0},{"id":26,"title":"Top 50 Most Frequently Asked String Coding Problems (Interview Preparation )","url":"top-50-most-frequently-asked-string-coding-problems-interview-preparation","description":null,"seoDescription":"","contentType":5,"generatedOn":"2026-10-14T22:54:36.7785229Z","viewCount":0},{"id":25,"title":"Intersection of Two Sorted Arrays","url":"intersection-of-two-sorted-arrays","description":null,"seoDescription":"","contentType":5,"generatedOn":"2026-10-14T22:54:36.7785245Z","viewCount":0}]}}},"source":{"isMobile":false}}; window.__CLIENT_RENDER__ = false;

Longest Playlist With No Repeated Songs : Brute Force to Optimal

Understanding the Problem First

Approach 1: Brute Force (Check Every Window)

Dry Run

Why It Works

Complexity

Approach 2: Sliding Window with HashSet

Dry Run

Extension: Printing the Actual Playlist

Why It Works

Complexity

Approach 3: Sliding Window with HashMap

Dry Run

Extension: Printing the Actual Playlist

Why This Is the Optimal Approach

Complexity

Comparing All Approaches

Key Takeaways

Trending Developer Reads

Understanding the Problem First

Approach 1: Brute Force (Check Every Window)

Dry Run

Why It Works

Complexity

Approach 2: Sliding Window with HashSet

Dry Run

Extension: Printing the Actual Playlist

Why It Works

Complexity

Approach 3: Sliding Window with HashMap

Dry Run

Extension: Printing the Actual Playlist

Why This Is the Optimal Approach

Complexity

Comparing All Approaches

Key Takeaways