Longest Substring Without Repeating Characters

Problem

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

A substring is a contiguous block of characters inside the string.

Intuition

The naive solution checks every substring and tests whether it contains duplicates. That is quadratic at best, and the duplicate check inside each window can make it worse.

The key observation is that a duplicate only matters if it lies inside the current window. If the same character appeared earlier but is now outside the window, it is irrelevant.

That means we do not need to "search the whole window" every time. We only need to remember the most recent position of each character. When we see a repeated character, we jump the left edge of the window just past the previous occurrence.

That jump is the entire trick. The left pointer never moves backward, so the window expands and contracts in linear time.

Approach

impl Solution {
    pub fn length_of_longest_substring(s: String) -> i32 {
        let bytes = s.as_bytes();
        let mut last = [-1i32; 128];
        let mut left = 0usize;
        let mut best = 0usize;

        for (right, &b) in bytes.iter().enumerate() {
            let idx = b as usize;
            if last[idx] >= left as i32 {
                left = (last[idx] + 1) as usize;
            }

            last[idx] = right as i32;
            best = best.max(right - left + 1);
        }

        best as i32
    }
}

function lengthOfLongestSubstring(s: string): number {
  const last = new Array<number>(128).fill(-1);
  let left = 0;
  let best = 0;

  for (let right = 0; right < s.length; right++) {
    const idx= s.charCodeAt(right);
    left= Math.max(left, last[idx] + 1);
    last[idx]= right;
    best= Math.max(best, right - left + 1);
  }

  return best;
}

Trace

For s = "abcabcbb":

The window never rescans old characters. Each index is processed once.

Edge cases

• Empty string returns 0.
• All characters identical returns 1.
• Duplicate outside the current window does not force a shrink, because left only jumps forward.
• Large alphabet can use a HashMap / Map instead of a fixed array if the input is not limited to ASCII.

Takeaway

Sliding window is not "two pointers with a vibe." It is a loop that maintains an explicit invariant.

For this problem, the invariant is "no duplicate characters inside the window." Once that is true, the longest valid substring seen so far is easy to track, and every character only enters and leaves the window once.