Problem · LC 3

Longest Substring Without Repeating Characters

Medium
◧ Classic · sliding window with hashset→ Expanding

How to recognize it

Find the longest substring with no duplicate characters. Signal: "longest substring", "no repeating", "unique characters". Classic sliding window setup.

The core idea

Use a sliding window (left and right pointers) with a set to track characters in the current window. Expand right, and if a duplicate is found, shrink from the left until the duplicate is gone. Track max length.

Why It's Tricky

Knowing WHEN to move the left pointer is key. You move it not just when a duplicate enters, but specifically until that duplicate is removed from the window.

The Key Insight

Maintain a set of characters in the current window. Expand right freely. When you hit a duplicate, shrink left until the duplicate is no longer in the set. Record the max window size along the way.

Step-by-Step Walkthrough

Example: "abcabcbb"

Window [a] → [ab] → [abc] → [a,b,c] = 3
Next char "a" is duplicate, shrink: [bc] → [bca] → [bca] = 3
Next "b" is duplicate, shrink: [cab] → [cab] = 3
Continue... max = 3 ("abc")

time O(n)
space O(min(n, charset_size))
longest_substring_without_repeating_characters
def lengthOfLongestSubstring(s):
    char_set = set()
    left = 0
    max_length = 0
    for right in range(len(s)):
        while s[right] in char_set:
            char_set.remove(s[left])
            left += 1
        char_set.add(s[right])
        max_length = max(max_length, right - left + 1)
    return max_length

Interview gotchas

  • Moving the left pointer: don't just move once; keep moving until the duplicate is gone.
  • Don't remove from set until the character actually moves out of the window.
  • Track max length at each step, not just at the end.

💡 What to Say in the Interview

  • Say: "I'll use a sliding window with a set to track unique chars."
  • Explain: "Expand right. If duplicate, shrink left until it's gone."
  • Key: "The set represents chars in the current window."
  • Complexity: "O(n) time (each char entered/removed once), O(min(n, charset_size)) space."

↳Variants they'll pivot to

Solve the base problem, then interviewers escalate. These are the usual next steps — knowing the connection is worth more than memorizing each.