LeetCode 3: Longest Substring Without Repeating Characters

Problem Statement

LeetCode 3, Longest Substring Without Repeating Characters, is a medium-level challenge that asks you to find the length of the longest chunk of a string where no character repeats. You’re given a string s, and a substring is a continuous piece of it (no skipping letters). The goal is to figure out how long the longest substring can be without any letter appearing more than once, returning just the number of characters in that substring.

Constraints

  • 0 <= s.length <= 5 * 10^4: The string can be empty or up to 50,000 characters.
  • s can have English letters, digits, symbols, and spaces.
  • Output is an integer (the length).

Example

Input: s = "abcabcbb"
Output: 3
Explanation: "abc" is the longest substring with no repeats (length 3).

Input: s = "bbbbb"
Output: 1
Explanation: "b" is the longest with no repeats (length 1).

Input: s = "pwwkew"
Output: 3
Explanation: "wke" is the longest with no repeats (length 3).

Understanding the Problem

We need to find a stretch of the string where every character is unique, and we want the longest one possible. For example, in "abcabcbb", "abc" works because a, b, and c are all different, and it’s 3 letters long—nothing longer fits the rule. It’s about sliding through the string, keeping track of what we’ve seen, and measuring the biggest chunk without repeats. We’ll use:

  • Sliding Window with Hash Map: A smart way to track characters and lengths.

Solution: Sliding Window with Hash Map

Explanation

Think of this like sliding a window over the string, growing it when we can add new letters and shrinking it when we hit a repeat. We use a hash map (like a notebook) to remember where we last saw each letter, so we know when to adjust the window.

  1. Initialize Variables.
  • Start with a left edge (start) at 0, a max length at 0, and an empty notebook to track letters and their positions.

2. Move Through the String.

  • Go letter by letter with an end pointer, checking each one.
  • If we see a letter already in our window, slide the start past its last spot.
  • Update the notebook with the letter’s new spot.
  • Measure the window size and keep the biggest one.

3. Return Result.

  • After checking all letters, return the longest window size found.

Step-by-Step Example

Example 1: s = "abcabcbb"

We have the string "abcabcbb" and want the longest piece with no repeats.

  • Goal: Find the longest stretch where every letter is different.
  • Result for reference: "abc" is 3 letters long with no repeats, and nothing longer works, so the answer is 3.
  • Start: Left edge at 0, max length at 0, notebook empty.
  • Step 1: Letter a (position 0).
    • Notebook is empty, no a yet. Add a: 0.
    • Window is from 0 to 0, size 1. Max is 1.
  • Step 2: Letter b (position 1).
    • No b in notebook. Add b: 1.
    • Window is 0 to 1, size 2. Max is 2.
  • Step 3: Letter c (position 2).
    • No c. Add c: 2.
    • Window is 0 to 2, size 3. Max is 3.
  • Step 4: Letter a (position 3).
    • a is in notebook at 0, which is in our window (0 to 2). Move start to 1 (past 0).
    • Update a: 3.
    • Window is 1 to 3, size 3. Max stays 3.
  • Step 5: Letter b (position 4).
    • b at 1 is in window (1 to 3). Move start to 2.
    • Update b: 4.
    • Window is 2 to 4, size 3. Max stays 3.
  • Step 6: Letter c (position 5).
    • c at 2 is in window (2 to 4). Move start to 3.
    • Update c: 5.
    • Window is 3 to 5, size 3. Max stays 3.
  • Step 7: Letter b (position 6).
    • b at 4 is in window (3 to 5). Move start to 5.
    • Update b: 6.
    • Window is 5 to 6, size 2. Max stays 3.
  • Step 8: Letter b (position 7).
    • b at 6 is in window (5 to 6). Move start to 7.
    • Update b: 7.
    • Window is 7 to 7, size 1. Max stays 3.
  • Finish: All letters checked, max length is 3.
  • Result: Return 3, matching "abc".

Example 2: s = "pwwkew"

Now, the string is "pwwkew", and we want the longest no-repeat stretch.

  • Goal: Find the longest piece with all unique letters.
  • Result for reference: "wke" is 3 letters with no repeats, so the answer is 3 ("pwke" has a repeat w).
  • Start: Left edge at 0, max length at 0, notebook empty.
  • Step 1: Letter p (position 0).
    • No p. Add p: 0.
    • Window is 0 to 0, size 1. Max is 1.
  • Step 2: Letter w (position 1).
    • No w. Add w: 1.
    • Window is 0 to 1, size 2. Max is 2.
  • Step 3: Letter w (position 2).
    • w at 1 is in window (0 to 1). Move start to 2.
    • Update w: 2.
    • Window is 2 to 2, size 1. Max stays 2.
  • Step 4: Letter k (position 3).
    • No k. Add k: 3.
    • Window is 2 to 3, size 2. Max stays 2.
  • Step 5: Letter e (position 4).
    • No e. Add e: 4.
    • Window is 2 to 4, size 3. Max is 3.
  • Step 6: Letter w (position 5).
    • w at 2 is in window (2 to 4). Move start to 3.
    • Update w: 5.
    • Window is 3 to 5, size 3. Max stays 3.
  • Finish: Done, max length is 3.
  • Result: Return 3, matching "wke".

Code

def lengthOfLongestSubstring(s: str) -> int:
    if not s:
        return 0

    char_index_map = {}
    start = 0
    max_length = 0

    for end in range(len(s)):
        if s[end] in char_index_map and char_index_map[s[end]] >= start:
            start = char_index_map[s[end]] + 1
        else:
            current_length = end - start + 1
            max_length = max(max_length, current_length)

        char_index_map[s[end]] = end

    return max_length

Complexity

  • Time Complexity: O(n) – One pass through the string, with fast notebook lookups.
  • Space Complexity: O(min(m, n)) – Notebook size depends on unique characters (m) or string length (n).

Efficiency Notes

This method is fast and smart, using the sliding window to avoid rechecking parts of the string, making it great for big inputs.

Alternative: Brute Force (Brief Mention)

Explanation

A basic way would be to check every possible substring and count unique letters, but that’s O(n³)—way too slow for large strings, so we skip it for the sliding window approach.

Additional Example

For s = "dvdf":

  • Goal: Longest no-repeat stretch.
  • Result for reference: "vdf" is 3 letters.
  • Step 1: d -> {d: 0}, size 1.
  • Step 2: v -> {d: 0, v: 1}, size 2.
  • Step 3: d -> Move start to 1, {d: 2, v: 1}, size 2.
  • Step 4: f -> {d: 2, v: 1, f: 3}, size 3.
  • Result: 3, matching "vdf".

Edge Cases

  • Empty String: s = "" – Returns 0.
  • All Same: s = "aaaaa" – Returns 1.
  • Spaces: s = "a b" – Works fine.

Final Thoughts

  • Sliding Window: Clever and efficient, a key skill for string problems.
  • Practice Value: Helps with other window-based challenges like finding substrings with limits.