Longest Substring Without Repeating Characters (LC 3)

Pattern: Sliding Window + Hash Map
Difficulty: Medium
Key Concept: For each right, move left just past the previous index of s[right] so the window never holds duplicates.

Problem Statement

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

Input

• s: String — may be empty; characters are often ASCII letters, digits, symbols, or spaces per constraints

Output

• int — maximum length of a substring with all distinct characters

Example

• s = "abcabcbb" → 3 ("abc")
• s = "bbbbb" → 1
• s = "pwwkew" → 3 ("wke")

---

1. Algorithm & Pseudocode

Brute force

For every pair (i, j) with i <= j, check if s[i..j] has all unique characters (e.g. with a Set or boolean array), track max length.

maxLen = 0
for i from 0 to n-1:
    seen = empty set
    for j from i to n-1:
        if s[j] in seen: break
        add s[j] to seen
        maxLen = max(maxLen, j - i + 1)
return maxLen

Optimal

Maintain window [left, right] and a map char → last index. When s[right] was seen inside the current window, jump left to max(left, lastIndex + 1).

map = empty
left = 0
maxLen = 0
for right from 0 to n-1:
    ch = s[right]
    if ch in map and map[ch] >= left:
        left = map[ch] + 1
    map[ch] = right
    maxLen = max(maxLen, right - left + 1)
return maxLen

---

2. Step-by-Step Analysis (Beginner-Friendly)

1. Why brute is slow There are O(n²) substrings; each check can scan up to O(n) → roughly O(n³) if you rescan naively, or O(n²) with a smart inner loop that breaks on duplicate.

2. Why sliding window works If all characters in [left, right] are unique and s[right+1] duplicates something, any longer answer that includes that duplicate must start after the earlier duplicate. So left only moves forward.

3. Why max(left, lastIndex + 1) Old occurrences before left are irrelevant—they are outside the window. Only duplicates inside the window should shrink it.

4. Why store index, not just “seen” You need to know where to move left in one step.

---

3. The Dry Run

Sample: s = "abca". Optimal map of last index.

right	ch	last in map?	left before	new left	window	maxLen
0	a	no	0	0	a	1
1	b	no	0	0	ab	2
2	c	no	0	0	abc	3
3	a	yes, idx 0 ≥ 0	0	1	bca	3

Result: 3.

ASCII window

indices: 0 1 2 3
chars:   a b c a
         L     R  -> duplicate 'a' at 0, move L to 1

         a b c a
           L   R  window "bca"

---

4. Java Solution

Brute Force

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

class Solution {
    public int lengthOfLongestSubstring(String s) {
        int n = s.length();
        int maxLen = 0;
        for (int i = 0; i < n; i++) {
            Set<Character> seen = new HashSet<>();
            for (int j = i; j < n; j++) {
                char c = s.charAt(j);
                if (seen.contains(c)) {
                    break;
                }
                seen.add(c);
                maxLen = Math.max(maxLen, j - i + 1);
            }
        }
        return maxLen;
    }
}

Time: O(n²) worst case (nested loops; inner breaks early on repeat).
Space: O(min(n, alphabet)) for the set.

Optimal

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

class Solution {
    public int lengthOfLongestSubstring(String s) {
        Map<Character, Integer> last = new HashMap<>();
        int left = 0;
        int maxLen = 0;
        for (int right = 0; right < s.length(); right++) {
            char c = s.charAt(right);
            if (last.containsKey(c) && last.get(c) >= left) {
                left = last.get(c) + 1;
            }
            last.put(c, right);
            maxLen = Math.max(maxLen, right - left + 1);
        }
        return maxLen;
    }
}

Time: O(n) — each index visited by right once, left only increases.
Space: O(min(n, alphabet)).

ASCII optimization: For ASCII-only, int[128] storing last index is faster than HashMap.

---

5. The “Java vs. Others” Edge

• String.charAt Java strings are immutable; charAt is O(1) for random access (UTF-16 code units—fine for ASCII-style problems).
• HashMap<Character, Integer> Autoboxing has a cost; for interviews, mention int[128] when the charset is bounded.
• Python dict with the same logic is idiomatic; Java’s primitive array variant avoids boxing.

---

6. Complexity Summary

Approach	Time	Space	Notes
Brute Force	O(n²)	O(σ)	σ = charset size; set per start.
Optimal sliding window	O(n)	O(σ)	left never moves backward.
Optimal + int[128]	O(n)	O(1)	Fixed table for ASCII.