34. Longest Substring Without Repeating Characters

🔗 LeetCode Problem: 3. Longest Substring Without Repeating Characters
📊 Difficulty: Medium
🏷️ Topics: Hash Table, String, Sliding Window

Problem Statement

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

Example 1:

Input: s = "abcabcbb"
Output: 3
Explanation: The answer is "abc", with the length of 3.

Example 2:

Input: s = "bbbbb"
Output: 1
Explanation: The answer is "b", with the length of 1.

Example 3:

Input: s = "pwwkew"
Output: 3
Explanation: The answer is "wke", with the length of 3.
Notice that the answer must be a substring, "pwke" is a subsequence and not a substring.

Constraints: - 0 <= s.length <= 5 * 10^4 - s consists of English letters, digits, symbols and spaces.

---

🎨 Visual Understanding

The Problem Visualized

s = "abcabcbb"

All substrings without repeating characters:
"a"     → length 1
"ab"    → length 2
"abc"   → length 3 ✓ (longest)
"b"     → length 1
"bc"    → length 2
"bca"   → length 3 ✓
"c"     → length 1
"ca"    → length 2
"cab"   → length 3 ✓
"a"     → length 1
"ab"    → length 2
"abc"   → cannot extend (duplicate 'b')
"b"     → length 1
"bb"    → has duplicate 'b' ✗

Answer: 3 (multiple substrings of length 3)

Key Observation: Sliding Window

Use a sliding window to track current substring:

s = "abcabcbb"
     ^  ^
     L  R

Window: "abc" (no duplicates) → length 3

When we hit duplicate:
s = "abcabcbb"
     ^   ^
     L   R

Window: "abca" (has duplicate 'a')
→ Shrink from left until no duplicate

Visual process:
[a b c] → valid, length 3
[a b c] a → duplicate 'a', move left
  [b c a] → valid, length 3
  [b c a] b → duplicate 'b', move left
    [c a b] → valid, length 3

Why Sliding Window Works

Key insight: 
If substring s[i...j] has duplicates,
then s[i...j+1], s[i...j+2], etc. also have duplicates.

No need to check all starting positions!

Strategy:
1. Expand window (right pointer)
2. If duplicate found, shrink window (left pointer)
3. Track maximum length during process

---

🎯 Approach 1: Brute Force

The Most Natural Thinking 💭

Core Logic:

Check all possible substrings:
1. For each starting position i
2. For each ending position j (from i to end)
3. Check if s[i...j] has duplicates
4. Track maximum length

Why This Works: - Checks all possibilities - Guaranteed to find answer - Easy to understand

Why This Fails Requirements: - Time complexity O(n³) - Checking each substring for duplicates is O(n) - Too slow for large strings - Not optimal for interviews

Implementation

public int lengthOfLongestSubstring(String s) {
    int n = s.length();
    int maxLen = 0;

    // Try all substrings
    for (int i = 0; i < n; i++) {
        for (int j = i; j < n; j++) {
            if (allUnique(s, i, j)) {
                maxLen = Math.max(maxLen, j - i + 1);
            }
        }
    }

    return maxLen;
}

private boolean allUnique(String s, int start, int end) {
    Set<Character> seen = new HashSet<>();
    for (int i = start; i <= end; i++) {
        char c = s.charAt(i);
        if (seen.contains(c)) {
            return false;
        }
        seen.add(c);
    }
    return true;
}

⏰ Time: O(n³) - O(n²) substrings, each checked in O(n)
💾 Space: O(min(n, m)) where m is charset size

---

✅ Approach 2: Sliding Window with HashSet (Optimal)

The Breakthrough Insight 💡

Core Logic:

Use sliding window with HashSet to track characters:

1. Expand window: Add right character to set
2. If duplicate found: Remove left characters until no duplicate
3. Track maximum window size
4. Repeat until right reaches end

Key insight: No need to check all substrings
Only track current valid window

Visual Explanation:

s = "abcabcbb"

Step 1: [a] → set = {a}, max = 1
Step 2: [a b] → set = {a,b}, max = 2
Step 3: [a b c] → set = {a,b,c}, max = 3
Step 4: [a b c] a → 'a' already in set!
        Remove from left: [b c] a
        set = {b,c,a}, max = 3
Step 5: [b c a] b → 'b' already in set!
        Remove from left: [c a] b
        set = {c,a,b}, max = 3
...continue

Key: When duplicate found, keep removing from left
until duplicate is gone

Why This Works:

Sliding window maintains the invariant:
"All characters in current window are unique"

When we find duplicate:
1. The duplicate char is somewhere in [left, right-1]
2. Keep removing from left until duplicate is removed
3. Now window is valid again
4. Continue expanding

Time: O(n) - each character visited at most twice
(once by right, once by left)

Implementation

public int lengthOfLongestSubstring(String s) {
    int n = s.length();
    Set<Character> window = new HashSet<>();
    int left = 0;
    int maxLen = 0;

    for (int right = 0; right < n; right++) {
        char c = s.charAt(right);

        // If duplicate found, shrink window from left
        while (window.contains(c)) {
            window.remove(s.charAt(left));
            left++;
        }

        // Add current character to window
        window.add(c);

        // Update maximum length
        maxLen = Math.max(maxLen, right - left + 1);
    }

    return maxLen;
}

⏰ Time: O(n) - each character visited at most twice
💾 Space: O(min(n, m)) where m is charset size

---

✅ Approach 3: Sliding Window with HashMap (Optimized)

The Further Optimization 💡

Core Logic:

Instead of removing characters one by one,
jump left pointer directly to position after duplicate:

Use HashMap to store: character → last seen index

When duplicate found:
left = max(left, lastSeenIndex[char] + 1)

This skips unnecessary removals

Visual Explanation:

s = "abcabcbb"

Step 1-3: Process "abc"
          map = {a:0, b:1, c:2}
          maxLen = 3

Step 4: right=3, char='a'
        'a' seen at index 0
        Jump: left = max(0, 0+1) = 1
        map = {a:3, b:1, c:2}
        Window: [b c a]

Instead of removing 'a' one by one,
we jump left pointer directly past the previous 'a'

Implementation

public int lengthOfLongestSubstring(String s) {
    int n = s.length();
    Map<Character, Integer> lastSeen = new HashMap<>();
    int left = 0;
    int maxLen = 0;

    for (int right = 0; right < n; right++) {
        char c = s.charAt(right);

        // If character seen before and within current window
        if (lastSeen.containsKey(c)) {
            // Jump left pointer to position after last occurrence
            left = Math.max(left, lastSeen.get(c) + 1);
        }

        // Update last seen position
        lastSeen.put(c, right);

        // Update maximum length
        maxLen = Math.max(maxLen, right - left + 1);
    }

    return maxLen;
}

⏰ Time: O(n) - single pass through string
💾 Space: O(min(n, m)) where m is charset size

---

🔍 Step-by-Step Execution

Example: s = "abcabcbb"

Initial State:
═══════════════════════════════════════════════════════════════════
s = "abcabcbb"
left = 0, right = 0, maxLen = 0
window = {}


Step 1: right=0, char='a'
═══════════════════════════════════════════════════════════════════
'a' not in window
Add 'a': window = {a}
Window: [a]
maxLen = max(0, 0-0+1) = 1

left=0, right=0


Step 2: right=1, char='b'
═══════════════════════════════════════════════════════════════════
'b' not in window
Add 'b': window = {a, b}
Window: [a b]
maxLen = max(1, 1-0+1) = 2

left=0, right=1


Step 3: right=2, char='c'
═══════════════════════════════════════════════════════════════════
'c' not in window
Add 'c': window = {a, b, c}
Window: [a b c]
maxLen = max(2, 2-0+1) = 3

left=0, right=2


Step 4: right=3, char='a'
═══════════════════════════════════════════════════════════════════
'a' is in window! (duplicate found)

Shrink from left:
  Remove s[0]='a': window = {b, c}
  left = 1

Check again: 'a' not in window anymore
Add 'a': window = {b, c, a}
Window: [b c a]
maxLen = max(3, 3-1+1) = 3

left=1, right=3


Step 5: right=4, char='b'
═══════════════════════════════════════════════════════════════════
'b' is in window! (duplicate found)

Shrink from left:
  Remove s[1]='b': window = {c, a}
  left = 2

Check again: 'b' not in window anymore
Add 'b': window = {c, a, b}
Window: [c a b]
maxLen = max(3, 4-2+1) = 3

left=2, right=4


Step 6: right=5, char='c'
═══════════════════════════════════════════════════════════════════
'c' is in window! (duplicate found)

Shrink from left:
  Remove s[2]='c': window = {a, b}
  left = 3

Check again: 'c' not in window anymore
Add 'c': window = {a, b, c}
Window: [a b c]
maxLen = max(3, 5-3+1) = 3

left=3, right=5


Step 7: right=6, char='b'
═══════════════════════════════════════════════════════════════════
'b' is in window! (duplicate found)

Shrink from left:
  Remove s[3]='a': window = {b, c}
  left = 4

Check again: 'b' still in window!
  Remove s[4]='b': window = {c}
  left = 5

Check again: 'b' not in window anymore
Add 'b': window = {c, b}
Window: [c b]
maxLen = max(3, 6-5+1) = 2 (no update)

left=5, right=6


Step 8: right=7, char='b'
═══════════════════════════════════════════════════════════════════
'b' is in window! (duplicate found)

Shrink from left:
  Remove s[5]='c': window = {b}
  left = 6

Check again: 'b' still in window!
  Remove s[6]='b': window = {}
  left = 7

Check again: 'b' not in window anymore
Add 'b': window = {b}
Window: [b]
maxLen = max(3, 7-7+1) = 1 (no update)

left=7, right=7


═══════════════════════════════════════════════════════════════════
🎯 FINAL RESULT: 3
═══════════════════════════════════════════════════════════════════

Example with HashMap Optimization: s = "abba"

Using HashMap approach:

Step 1: right=0, 'a'
        lastSeen = {a:0}
        left = 0, maxLen = 1

Step 2: right=1, 'b'
        lastSeen = {a:0, b:1}
        left = 0, maxLen = 2

Step 3: right=2, 'b' (duplicate!)
        'b' last seen at index 1
        left = max(0, 1+1) = 2
        lastSeen = {a:0, b:2}
        maxLen = max(2, 2-2+1) = 2

        Direct jump! No need to remove one by one

Step 4: right=3, 'a' (duplicate!)
        'a' last seen at index 0
        left = max(2, 0+1) = 2 (stay at 2)
        lastSeen = {a:3, b:2}
        maxLen = max(2, 3-2+1) = 2

Result: 2

---

🔍 Edge Cases

Case 1: Empty string
Input: s = ""
Output: 0

Case 2: Single character
Input: s = "a"
Output: 1

Case 3: All same characters
Input: s = "aaaaa"
Output: 1
Explanation: Any single character

Case 4: All unique characters
Input: s = "abcdef"
Output: 6
Explanation: Entire string

Case 5: Duplicate at start
Input: s = "aab"
Output: 2
Explanation: "ab"

Case 6: Duplicate at end
Input: s = "aba"
Output: 2
Explanation: "ab" or "ba"

Case 7: With spaces and symbols
Input: s = "a b!a"
Output: 4
Explanation: " b!a" (space is a character)

Case 8: Long string with one duplicate
Input: s = "abcdefghijka"
Output: 11
Explanation: "bcdefghijk"

---

Common Mistakes

Mistake 1: Not handling empty string
❌ Wrong: 
    int left = 0, right = 0;
    // What if s.length() == 0?
✓ Right: 
    if (s == null || s.length() == 0) return 0;
Reason: Need to check edge case

Mistake 2: Wrong window size calculation
❌ Wrong: 
    maxLen = Math.max(maxLen, right - left);
✓ Right: 
    maxLen = Math.max(maxLen, right - left + 1);
Reason: Need +1 for inclusive range

Mistake 3: Not removing from HashSet properly
❌ Wrong: 
    while (window.contains(c)) {
        left++;  // Forgot to remove!
    }
✓ Right: 
    while (window.contains(c)) {
        window.remove(s.charAt(left));
        left++;
    }
Reason: Must update window along with pointer

Mistake 4: Wrong left pointer update in HashMap approach
❌ Wrong: 
    if (lastSeen.containsKey(c)) {
        left = lastSeen.get(c) + 1;  // Missing max!
    }
✓ Right: 
    if (lastSeen.containsKey(c)) {
        left = Math.max(left, lastSeen.get(c) + 1);
    }
Reason: Previous occurrence might be outside current window

Mistake 5: Checking window.contains after adding
❌ Wrong: 
    window.add(c);
    while (window.contains(c)) {
        // This will always be true!
    }
✓ Right: 
    while (window.contains(c)) {
        // Check before adding
    }
    window.add(c);
Reason: Check duplicate before adding new character

Mistake 6: Not updating maxLen at right position
❌ Wrong: 
    if (right - left + 1 > maxLen) {
        maxLen = right - left + 1;
    }
    // Placed after adding to window
✓ Right: 
    window.add(c);
    maxLen = Math.max(maxLen, right - left + 1);
    // Update after window is valid
Reason: Update after ensuring window is valid

---

🎯 Key Takeaways

⚡ Algorithm Comparison

Approach 1: Brute Force
  Time: O(n³)
  Space: O(min(n, m))
  Use: Only for understanding

Approach 2: Sliding Window + HashSet (RECOMMENDED)
  Time: O(n)
  Space: O(min(n, m))
  Use: Clean and intuitive

Approach 3: Sliding Window + HashMap
  Time: O(n)
  Space: O(min(n, m))
  Use: Slightly optimized, fewer operations

🔑 The Core Insight

Sliding Window Pattern:
1. Expand window by moving right pointer
2. When duplicate found, shrink from left
3. Maintain invariant: all chars in window are unique
4. Track maximum window size

Two Variants:

HashSet Approach:
- Store characters in window
- When duplicate: remove from left until gone
- Simple and intuitive

HashMap Approach:
- Store character → last seen index
- When duplicate: jump left pointer directly
- Fewer operations (no while loop for removal)

Time Complexity:
Both O(n) - each character visited at most twice
- Right pointer visits each char once
- Left pointer visits each char at most once

Key Insight:
If s[i..j] has duplicate, then s[i..j+1], s[i..j+2] also have duplicate
No need to check all substrings!

🎯 Pattern Recognition

Problem Type: Substring with Constraints
Core Pattern: Sliding Window

When to Apply:
✓ Finding substring/subarray with specific property
✓ Need to track elements in current window
✓ Can expand and shrink window dynamically
✓ Want O(n) time complexity

Key Techniques:
→ Two pointers (left, right) for window
→ HashSet/HashMap to track window elements
→ Expand window: right++
→ Shrink window: left++ (when constraint violated)
→ Track optimum during process

Related Problems:
- Minimum Window Substring (LC 76)
- Longest Substring with At Most K Distinct Characters (LC 340)
- Longest Repeating Character Replacement (LC 424)
- Find All Anagrams in a String (LC 438)

🧠 Interview Strategy

Step 1: "Need longest substring without repeating chars"
Step 2: "Use sliding window with two pointers"
Step 3: "HashSet to track characters in window"
Step 4: "Expand until duplicate, then shrink"
Step 5: "O(n) time, each char visited at most twice"

Key Points to Mention:
- Sliding window technique
- HashSet for duplicate detection
- Two pointers expand/shrink window
- Track maximum during process
- O(n) time, O(m) space where m is charset size
- Can optimize with HashMap to jump left pointer

---

📝 Quick Revision Notes

🎯 Core Concept:

Use sliding window with HashSet to track unique characters. Expand window with right pointer, shrink when duplicate found with left pointer.

⚡ Quick Implementation (HashSet):

public int lengthOfLongestSubstring(String s) {
    Set<Character> window = new HashSet<>();
    int left = 0, maxLen = 0;

    for (int right = 0; right < s.length(); right++) {
        char c = s.charAt(right);

        // Remove from left until no duplicate
        while (window.contains(c)) {
            window.remove(s.charAt(left));
            left++;
        }

        // Add current character
        window.add(c);

        // Update maximum
        maxLen = Math.max(maxLen, right - left + 1);
    }

    return maxLen;
}

⚡ Quick Implementation (HashMap - Optimized):

public int lengthOfLongestSubstring(String s) {
    int len = s.length();
    int left = 0;
    int right = 0;
    int res = 0;
    HashMap<Character, Integer> lastSeenIndex = new HashMap<>();

    while(right < len) {
        char ch = s.charAt(right);
        if(lastSeenIndex.containsKey(ch)) {
            // why max (left, lastSeenIndex.get(ch) + 1)?
            // Take "abba". Post processing i = 2 (b), left - 2 
            // and right = 2 and map: {a: 0, b: 2}
            // Now, when we process i = 3, left becomes 0 + 1 = 1
            // which is wrong because we cannot go back. Hence, max of
            // existing left and lastSeenIndex
            left = Math.max(left, lastSeenIndex.get(ch) + 1);
        }

        lastSeenIndex.put(ch, right);
        res = Math.max(res, right - left + 1);
        right++;
    }

    return res;
}

🔑 Key Insights:

• Sliding window: Two pointers (left, right) create dynamic window
• HashSet approach: Check if char in set, remove from left until unique
• HashMap approach: Jump left directly to position after duplicate
• Expand: right++ adds character to window
• Shrink: left++ removes character when duplicate found
• Window size: right - left + 1 (inclusive)
• Update maxLen: After ensuring window is valid
• Time: O(n) - each char visited at most twice
• Space: O(min(n, m)) where m is charset size
• Key: Maintain invariant - all chars in window are unique

🎪 Memory Aid:

"Expand till DUPLICATE, shrink till UNIQUE, track MAX!"
Think: "Sliding window slides, HashSet checks, no repeats allowed"

---

Related Patterns

• Minimum Window Substring (LC 76)
• Longest Substring with At Most K Distinct Characters (LC 340)
• Longest Repeating Character Replacement (LC 424)
• Find All Anagrams in a String (LC 438)

---

Happy practicing! 🎯