Longest Substring Without Repeating Characters

The brute-force way is to check every substring for duplicates. The key insight for the optimal approach: maintain a window [left, right] that never contains a duplicate. When extending right would introduce a duplicate, do not restart from scratch — just slide left forward past the previous occurrence of that character. A hash map from character to its last-seen index makes that jump O(1).

Brute Force

Time O(n³)Space O(min(n, m))

For every starting index i, grow j outward while a set of seen characters stays duplicate-free, tracking the best length found.

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        n = len(s)
        best = 0
        for i in range(n):
            seen = set()
            for j in range(i, n):
                if s[j] in seen:
                    break
                seen.add(s[j])
                best = max(best, j - i + 1)
        return best

Why it’s slow: for each of the n starting indices we rebuild a fresh set and rescan forward, so building every substring costs O(n²) substrings times O(n) work to check each one — O(n³) overall (or O(n²) with the early break, but still redundant: index i+1 recomputes everything index i already knew about the same characters).

Sliding Window (Hash Map)

OptimalTime O(n)Space O(min(n, m))

Walk right across the string once. Keep a map of character -> last index seen. If the character at right was last seen at or after left, it is a duplicate inside the current window — jump left to one past that occurrence. Otherwise the window is still duplicate-free. Either way, update the map and check if the current window [left, right] is the longest so far.

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        seen = {}  # char -> last index seen
        left = 0
        best = 0
        for right, ch in enumerate(s):
            if ch in seen and seen[ch] >= left:
                left = seen[ch] + 1
            seen[ch] = right
            best = max(best, right - left + 1)
        return best

Tracing s = "abcabcbb":

leftright

best = 1

1 / 8

comparingseencurrentdiscarded

a is new. Window [0,0], best = 1.

Correctness: left only ever moves forward, and it always jumps to exactly one past the most recent duplicate, so [left, right] is always the longest duplicate-free window ending at right. Every window length is checked, so the true maximum is found.

Complexity: each index is visited by right exactly once and by left at most once, so the total work is O(n). The map holds at most min(n, m) entries, where m is the size of the character set — O(min(n, m)) space.