DSA With AI
Week 2 ยท Sliding Window

Longest Substring Without Repeating Characters

Find the length of the longest contiguous substring with no repeated characters.

Medium Sliding Window Week 2 Practice runner

Frame the problem

  • The substring must be contiguous.
  • Characters can repeat elsewhere outside the window.
  • You need the maximum length, not the substring itself.
1. Reveal example inputs and outputs

Example 1

Input:

length_of_longest_substring("abcabcbb")

Output:

3

Example 2

Input:

length_of_longest_substring("bbbbb")

Output:

1
2. Brute force first

How would you test every substring? Which repeated-character information lets you move the left boundary directly?

3. Reveal the insight ladder
  1. Keep a sliding window with unique characters.
  2. Map each character to its most recent index.
  3. When a repeat appears inside the window, move left after the previous occurrence.
  4. Update best length after the window is valid.
4. Dry run before code
  1. s = abcabcbb.
  2. abc reaches length 3.
  3. The next a moves left from 0 to 1, preserving bca.
  4. No later valid window exceeds 3.
5. Reveal final Python solution 
def length_of_longest_substring(s):
    last_seen = {}
    left = 0
    best = 0
    for right, char in enumerate(s):
        if char in last_seen and last_seen[char] >= left:
            left = last_seen[char] + 1
        last_seen[char] = right
        best = max(best, right - left + 1)
    return best

Complexity: Time O(n), space O(k), where k is the number of distinct characters in the window/map.

Interview narration

  • The left pointer only moves forward.
  • The map tells me whether a repeat is inside the current window.
  • I update length only after repairing the invariant.

Common traps

  • Treating the answer as a subsequence.
  • Moving left backward because of an old occurrence before the window.
  • Updating best before fixing duplicates.

Follow-up drills

1. How would you return the substring too?

Track best_start along with best length whenever a new maximum is found, then slice s[best_start:best_start + best].

2. What if the input is a stream?

The sliding-window map still works for length; returning the substring may require buffering the current/best window.

Interactive runner

Write the required Python function. Your code runs locally in this browser. Hints reveal one failing case at a time.