Longest Substring Without Repeating Characters

Learning goal: Recognize the exact property that makes a substring valid and identify what must be maximized.

Core idea We examine contiguous windows of the input string. A window is valid when no character occurs twice inside it. The task is to maximize the window width, not to rearrange characters or select arbitrary positions.

Algorithm plan

• Keep a left boundary and expand a right boundary across the string.
• Track the longest valid width seen so far.
• When a repeated character appears, repair the window before measuring it again.

Micro-example For abcabcbb, the first window grows as a, ab, abc. The next a repeats, so the window must move past the earlier a.

Pitfalls

• A substring must be contiguous; skipping characters changes the problem.
• The answer can be zero when the input is empty.
• The longest valid window may occur in the middle rather than at either endpoint.

Recap

• Valid means all characters in one contiguous window are distinct.
• The answer is the maximum width of any valid window.
• A moving window avoids checking every substring from scratch.

Learning goal: Understand why a repeated character moves left directly instead of shrinking one character at a time.

Core idea Store the most recent index of every character in lastIndex. When s[right] repeats inside the current window, every window starting at or before its previous position is invalid. We can therefore jump left to one position after that previous occurrence.

Algorithm plan

• Read the incoming character at right.
• Look up its previous index in lastIndex.
• If that index is at least left, set left = previousIndex + 1.
• Record the current index as the character's newest position.
• Update best with right - left + 1.

Micro-example In abca, the final a was previously at index 0. The window starts at 0, so jump left to 0 + 1 = 1, producing bca.

Pitfalls

• Set left to lastIndex[c] + 1, never merely lastIndex[c].
• A previous occurrence may be stale and lie before the current window.
• Updating lastIndex must happen after using its old value for the jump.

Recap

• Expand at right.
• Jump past an in-window duplicate.
• Store the newest index and measure the repaired window.

Learning goal: Translate the sliding-window idea into a linear-time algorithm.

Core idea Each character is processed once as the right edge advances. The left edge only moves forward, and the map lets us move it directly to the first position after a duplicate. Because neither pointer moves backward, the total pointer movement is linear.

Algorithm plan

left = 0
best = 0
lastIndex = empty map
for right from 0 through n - 1:
    c = s[right]
    if c is in lastIndex and lastIndex[c] >= left:
        left = lastIndex[c] + 1
    lastIndex[c] = right
    best = max(best, right - left + 1)
return best

Micro-example For abcabcbb, after processing the second a, left jumps from 0 to 1. The window becomes bca, whose width remains 3.

Pitfalls

• Check lastIndex[c] >= left; an older index outside the window should not move left backward.
• Compute the width after repairing the window.
• Keep the latest index even when a repeat was found.

Recap

• One pass over the string is sufficient.
• The map supports constant-time last-position lookup.
• The invariant is a duplicate-free window after every iteration.

Learning goal: Trace every pointer movement and see how the answer emerges from valid window widths.

Core idea We process abcabcbb from left to right. The first three characters create a width-3 window. Each later repeat causes a jump that preserves the invariant instead of restarting the scan.

Pointer movement

Micro-example At index 6, b was last seen at index 4, which is inside the current window starting at 3. Jump to left = 5; the repaired window is cb.

Pitfalls

• Do not erase the whole map when a duplicate appears.
• Do not confuse the character's previous index with the new window's left boundary.
• A repeat can shrink the window without reducing the best answer.

Recap

• The maximum width reached is 3.
• Repeats at indices 3, 4, 5, and 6 trigger jumps.
• The final answer is already known even though scanning continues.

Learning goal: Debug the two pointer mistakes that most often break this solution.

Core idea The map's indices are global, while the window is local. A stored index is useful for moving left only when it lies inside the current window. The left boundary must also move one position beyond the duplicate so that duplicate is excluded.

Correct duplicate test

Use lastIndex[c] >= left, then assign left = lastIndex[c] + 1. If lastIndex[c] < left, the old occurrence is stale and should be ignored.

Micro-example Suppose left = 5 and the incoming character was last seen at index 2. That occurrence is outside the window, so left stays 5. Moving it backward would reintroduce repeated characters.

Pitfalls

• Do not move left backward because of a stale index.
• Do not update best before repairing a repeated-character window.
• Test empty strings, one-character strings, all-unique strings, and all-identical strings.

Recap

• The duplicate must be removed from the active window.
• Stale map entries cannot affect the current window.
• These checks preserve the invariant on every iteration.

Learning goal: Justify the linear runtime and connect the implementation to the problem's target bounds.

Core idea The right pointer visits each character once. The left pointer also moves only forward, so across the entire scan it advances at most n times. Hash-map lookups and updates are expected O(1), giving an overall O(n) time algorithm.

Complexity

The map stores one latest index per distinct character. Therefore its space is O(min(n, alphabet)): it cannot contain more distinct keys than the string length or the available alphabet.

Micro-example For abcabcbb, eight characters are processed, but no character is repeatedly scanned from the beginning. Each repeat causes one direct boundary jump.

Pitfalls

• Do not claim O(1) space unless the alphabet is explicitly fixed and bounded.
• Do not use nested loops that restart after each duplicate.
• Expected constant-time hashing assumes a standard hash-map implementation.

Recap

• Time: O(n).
• Space: O(min(n, alphabet)).
• The invariant plus last-index jumps produces both correctness and efficiency.