3. Longest Substring Without Repeating Characters (Medium)

Problem

Given a string s, find the length of the longest substring without repeating characters.

Example

• s = "abcabcbb" → 3 ("abc")
• s = "bbbbb" → 1
• s = "pwwkew" → 3 ("wke", substring, not subsequence)

LeetCode 3 · Link · Medium

Try it yourself

Python

▶ Run Python ↻ Reset

idle

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run Python to execute. First run downloads Python (~10 MB, cached after that).

TypeScript

▶ Run TS ↻ Reset

idle

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run TS to execute. First run downloads Babel (~400 KB, cached after that).

Go

▶ Run Go ↻ Reset

idle

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run Go to execute. Runs via the Go Playground API.

Approach 1: Brute force, check every substring

Enumerate every substring and check uniqueness.

Python

def length_of_longest_substring(s: str) -> int:
    best = 0
    n = len(s)
    for i in range(n):                               # L1: outer loop, n iterations
        for j in range(i, n):                        # L2: inner loop, up to n-i iterations
            if len(set(s[i:j + 1])) == j - i + 1:   # L3: slice + set construction, O(n) each
                best = max(best, j - i + 1)          # L4: O(1)
    return best

TypeScript

function lengthOfLongestSubstring(s: string): number {
    let best = 0;
    const n = s.length;
    for (let i = 0; i < n; i++) {                           // L1: outer loop, n iterations
        for (let j = i; j < n; j++) {                       // L2: inner loop, up to n-i iterations
            const sub = s.slice(i, j + 1);
            if (new Set(sub).size === j - i + 1) {          // L3: slice + Set, O(n) each
                best = Math.max(best, j - i + 1);           // L4: O(1)
            }
        }
    }
    return best;
}

Go

func lengthOfLongestSubstring(s string) int {
  best := 0
  n := len(s)
  for i := 0; i < n; i++ {                          // L1: outer loop, n iterations
    seen := make(map[byte]bool)
    for j := i; j < n; j++ {                      // L2: inner loop, up to n-i iterations
      seen[s[j]] = true
      if len(seen) == j-i+1 && j-i+1 > best {  // L3: set size check, O(1) amortized
        best = j - i + 1                      // L4: O(1)
      }
    }
  }
  return best
}

Swift

final class Solution {
    func lengthOfLongestSubstring(_ s: String) -> Int {
        let characters = Array(s)
        var best = 0
        for start in characters.indices {
            var seen: Set<Character> = []
            for end in start..<characters.count {
                guard seen.insert(characters[end]).inserted else { break }
                best = max(best, end - start + 1)
            }
        }
        return best
    }
}

Where the time goes, line by line

Variables: n = len(s), k = number of distinct characters in s (≤ alphabet size).

Line	Per-call cost	Times executed	Contribution
L1 (outer loop)	$O(1)$	n	$O(n)$
L2 (inner loop)	$O(1)$	$O(n²)$ total	$O(n²)$
L3 (slice + set)	$O(n)$	$O(n²)$	$O(n³)$ ← dominates
L4 (max update)	$O(1)$	$O(n²)$	$O(n²)$

L3 is the culprit: s[i:j+1] allocates a new string of length up to n, then set(...) scans it character by character. Both are $O(n)$, and we do this $O(n²)$ times.

Complexity

• Time: $O(n³)$, driven by L3 (slice + set on every substring pair).
• Space: $O(n)$ for the set per check.

Approach 2: Expanding window with set (check uniqueness incrementally)

For each starting index, expand rightward while the next character isn’t already in the set.

Python

def length_of_longest_substring(s: str) -> int:
    n = len(s)
    best = 0
    for i in range(n):                # L1: outer loop, n iterations
        seen = set()                   # L2: new set each start, O(1)
        for j in range(i, n):         # L3: inner loop, up to n-i iterations
            if s[j] in seen:          # L4: O(1) set membership
                break
            seen.add(s[j])            # L5: O(1) amortized
        best = max(best, len(seen))   # L6: O(1)
    return best

TypeScript

function lengthOfLongestSubstring(s: string): number {
    const n = s.length;
    let best = 0;
    for (let i = 0; i < n; i++) {              // L1: outer loop, n iterations
        const seen = new Set<string>();         // L2: new Set each start, O(1)
        for (let j = i; j < n; j++) {          // L3: inner loop, up to n-i iterations
            if (seen.has(s[j])) break;         // L4: O(1) Set membership
            seen.add(s[j]);                    // L5: O(1) amortized
        }
        best = Math.max(best, seen.size);      // L6: O(1)
    }
    return best;
}

Go

func lengthOfLongestSubstring(s string) int {
  n := len(s)
  best := 0
  for i := 0; i < n; i++ {                    // L1: outer loop, n iterations
    seen := make(map[byte]bool)              // L2: new map each start, O(1)
    for j := i; j < n; j++ {               // L3: inner loop, up to n-i iterations
      if seen[s[j]] {                     // L4: O(1) map membership
        break
      }
      seen[s[j]] = true                   // L5: O(1) amortized
    }
    if len(seen) > best {                   // L6: O(1)
      best = len(seen)
    }
  }
  return best
}

Swift

final class Solution {
    func lengthOfLongestSubstring(_ s: String) -> Int {
        let characters = Array(s)
        var seen: Set<Character> = []
        var left = 0, best = 0
        for right in characters.indices {
            while seen.contains(characters[right]) {
                seen.remove(characters[left])
                left += 1
            }
            seen.insert(characters[right])
            best = max(best, right - left + 1)
        }
        return best
    }
}

Where the time goes, line by line

Variables: n = len(s), k = number of distinct characters in s (≤ alphabet size).

Line	Per-call cost	Times executed	Contribution
L1 (outer loop)	$O(1)$	n	$O(n)$
L2 (set init)	$O(1)$	n	$O(n)$
L3/L4/L5 (inner loop)	$O(1)$ each	$O(n²)$ total	$O(n²)$ ← dominates
L6 (best update)	$O(1)$	n	$O(n)$

This is better than Approach 1 because there’s no slice allocation or full-set rebuild inside the inner loop: each s[j] in seen and seen.add(s[j]) is $O(1)$, so the total is purely the $O(n²)$ loop iterations.

Complexity

• Time: $O(n²)$, driven by L3/L4/L5 (the $O(n²)$ inner loop iterations).
• Space: $O(k)$ where k = distinct characters (≤ alphabet size).

Better than brute force, still not optimal.

Approach 3: Sliding window with last-seen map (optimal)

Maintain left (start of the current valid window) and a hash map last_seen[ch] = index. When the current character was last seen inside the current window, jump left to just past that last-seen index.

Python

def length_of_longest_substring(s: str) -> int:
    last_seen = {}                                        # L1: O(1)
    left = 0                                             # L2: O(1)
    best = 0                                             # L3: O(1)
    for right, ch in enumerate(s):                       # L4: outer loop, n iterations
        if ch in last_seen and last_seen[ch] >= left:    # L5: O(1) hash lookup
            left = last_seen[ch] + 1                     # L6: O(1) jump left
        last_seen[ch] = right                            # L7: O(1) update map
        best = max(best, right - left + 1)               # L8: O(1)
    return best

TypeScript

function lengthOfLongestSubstring(s: string): number {
    const lastSeen = new Map<string, number>();           // L1: O(1)
    let left = 0;                                        // L2: O(1)
    let best = 0;                                        // L3: O(1)
    for (let right = 0; right < s.length; right++) {    // L4: outer loop, n iterations
        const ch = s[right];
        if (lastSeen.has(ch) && lastSeen.get(ch)! >= left) {  // L5: O(1) map lookup
            left = lastSeen.get(ch)! + 1;               // L6: O(1) jump left
        }
        lastSeen.set(ch, right);                        // L7: O(1) update map
        best = Math.max(best, right - left + 1);        // L8: O(1)
    }
    return best;
}

Go

func lengthOfLongestSubstring(s string) int {
  lastSeen := make(map[rune]int)                       // L1: O(1)
  left := 0                                            // L2: O(1)
  best := 0                                            // L3: O(1)
  for right, ch := range s {                           // L4: outer loop, n iterations
    if idx, ok := lastSeen[ch]; ok && idx >= left { // L5: O(1) map lookup
      left = idx + 1                               // L6: O(1) jump left
    }
    lastSeen[ch] = right                             // L7: O(1) update map
    if right-left+1 > best {                         // L8: O(1)
      best = right - left + 1
    }
  }
  return best
}

Swift

final class Solution {
    func lengthOfLongestSubstring(_ s: String) -> Int {
        var lastSeen: [Character: Int] = [:]
        var left = 0, best = 0
        for (right, character) in s.enumerated() {
            if let previous = lastSeen[character], previous >= left { left = previous + 1 }
            lastSeen[character] = right
            best = max(best, right - left + 1)
        }
        return best
    }
}

Where the time goes, line by line

Variables: n = len(s), k = number of distinct characters in s (≤ alphabet size).

Line	Per-call cost	Times executed	Contribution
L1-L3 (init)	$O(1)$	1	$O(1)$
L4 (loop)	$O(1)$ body	n	$O(n)$ ← dominates
L5 (hash lookup)	$O(1)$	n	$O(n)$
L6 (jump left)	$O(1)$	at most n total	$O(n)$
L7 (map update)	$O(1)$	n	$O(n)$
L8 (best update)	$O(1)$	n	$O(n)$

The critical insight: left only ever moves forward. Across the entire run, left advances at most n times total, so all of L6 combined is $O(n)$, not $O(n)$ per iteration. Each character is visited by right exactly once and by left at most once.

Complexity

• Time: $O(n)$, driven by L4/L5/L7 (the single linear pass).
• Space: $O(k)$. Hash map bounded by alphabet size.

Try this approach:

Python

▶ Run Python ↻ Reset

idle

Click Run Python to execute. First run downloads Python (~10 MB, cached after that).

TypeScript

▶ Run TS ↻ Reset

idle

Click Run TS to execute. First run downloads Babel (~400 KB, cached after that).

Go

▶ Run Go ↻ Reset

idle

Click Run Go to execute. Runs via the Go Playground API.

Summary

Approach	Time	Space
Brute force	$O(n³)$	$O(n)$
Expanding window	$O(n²)$	$O(k)$
Sliding window + last-seen	$O(n)$	$O(k)$

The optimal approach is a variable-size sliding window whose invariant (no repeats in [left, right]) is preserved by jumping left instead of decrementing. Same pattern solves many substring problems.

Test cases

Python

# Quick smoke tests - paste into a REPL or save as test_003.py and run.
# Uses the optimal Approach 3 implementation.

def length_of_longest_substring(s: str) -> int:
    last_seen = {}
    left = 0
    best = 0
    for right, ch in enumerate(s):
        if ch in last_seen and last_seen[ch] >= left:
            left = last_seen[ch] + 1
        last_seen[ch] = right
        best = max(best, right - left + 1)
    return best

def _run_tests():
    assert length_of_longest_substring("abcabcbb") == 3   # "abc"
    assert length_of_longest_substring("bbbbb") == 1      # "b"
    assert length_of_longest_substring("pwwkew") == 3     # "wke"
    assert length_of_longest_substring("") == 0           # empty string
    assert length_of_longest_substring("a") == 1          # single char
    assert length_of_longest_substring("abcdef") == 6     # all unique
    print("all tests pass")

if __name__ == "__main__":
    _run_tests()

TypeScript

function lengthOfLongestSubstring(s: string): number {
    const lastSeen = new Map<string, number>();
    let left = 0;
    let best = 0;
    for (let right = 0; right < s.length; right++) {
        const ch = s[right];
        if (lastSeen.has(ch) && lastSeen.get(ch)! >= left) {
            left = lastSeen.get(ch)! + 1;
        }
        lastSeen.set(ch, right);
        best = Math.max(best, right - left + 1);
    }
    return best;
}

console.assert(lengthOfLongestSubstring("abcabcbb") === 3);
console.assert(lengthOfLongestSubstring("bbbbb") === 1);
console.assert(lengthOfLongestSubstring("pwwkew") === 3);
console.assert(lengthOfLongestSubstring("") === 0);
console.assert(lengthOfLongestSubstring("a") === 1);
console.assert(lengthOfLongestSubstring("abcdef") === 6);
console.log("all tests pass");

Go

func lengthOfLongestSubstring(s string) int {
  lastSeen := make(map[rune]int)
  left := 0
  best := 0
  for right, ch := range s {
    if idx, ok := lastSeen[ch]; ok && idx >= left {
      left = idx + 1
    }
    lastSeen[ch] = right
    if right-left+1 > best {
      best = right - left + 1
    }
  }
  return best
}

Related data structures

• Strings, input
• Hash Tables, last-seen index map (the optimal-pattern enabler)

Related concepts

• Sliding Window, the contiguous range invariant behind expanding and shrinking a window.
• Hash Map Counting, the lookup table pattern for complements, frequencies, and seen items.