Skip to main content

3. Longest Substring Without Repeating Characters

mediumAsked at AMD

Find the length of the longest substring with all unique characters. AMD uses sliding-window problems to test whether candidates can maintain state efficiently across a moving window — a pattern that appears in stream processing, cache eviction, and pipeline hazard detection.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Source citations

Public interview reports confirming this problem appears in AMD loops.

  • Glassdoor (2026-Q1)— AMD SWE interview reports cite sliding window problems as a staple in medium rounds, with this problem appearing regularly.
  • Blind (2025-10)— AMD prep posts list longest unique substring as a core sliding-window medium for SWE roles.

Problem

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

Constraints

  • 0 <= s.length <= 5 * 10^4
  • s consists of English letters, digits, symbols and spaces.

Examples

Example 1

Input
s = "abcabcbb"
Output
3

Explanation: "abc" is the longest substring without repeating characters.

Example 2

Input
s = "bbbbb"
Output
1

Explanation: "b" is the longest unique substring.

Example 3

Input
s = "pwwkew"
Output
3

Explanation: "wke" is the longest unique substring.

Approaches

1. Sliding Window with Map (jump optimization)

Maintain a window [left, right]. Store the last seen index of each character. When a repeat is found, jump left to max(left, lastSeen[ch] + 1) to skip the duplicate immediately.

Time
O(n)
Space
O(min(n, charset))
function lengthOfLongestSubstring(s) {
  const map = new Map(); // char -> last seen index
  let maxLen = 0;
  let left = 0;
  for (let right = 0; right < s.length; right++) {
    const ch = s[right];
    if (map.has(ch) && map.get(ch) >= left) {
      left = map.get(ch) + 1;
    }
    map.set(ch, right);
    maxLen = Math.max(maxLen, right - left + 1);
  }
  return maxLen;
}

Tradeoff: O(n) — each character is visited once. The jump (left = lastSeen + 1) avoids incrementing left one step at a time, which would still be O(n) total but requires an extra guard condition.

2. Sliding Window with Set

Use a Set to track characters in the current window. Shrink from the left by removing characters until the duplicate is gone.

Time
O(n)
Space
O(min(n, charset))
function lengthOfLongestSubstring(s) {
  const set = new Set();
  let left = 0, maxLen = 0;
  for (let right = 0; right < s.length; right++) {
    while (set.has(s[right])) {
      set.delete(s[left]);
      left++;
    }
    set.add(s[right]);
    maxLen = Math.max(maxLen, right - left + 1);
  }
  return maxLen;
}

Tradeoff: O(n) amortized — left moves at most n times total. Simpler to reason about but may do more work per character than the map-jump approach.

AMD-specific tips

Frame the sliding window as a hardware register window: you're maintaining a live view of which characters are currently 'loaded' in your window, and you evict from the left when you detect a collision. AMD engineers deal with register file conflicts and pipeline windows — this analogy resonates. Prefer the map-jump approach in interviews: jumping left directly instead of shrinking one step at a time demonstrates knowledge of how to minimize iterations.

Common mistakes

  • Not guarding `map.get(ch) >= left` — a character could be in the map from before the current window; without this check, left jumps backward.
  • Using s.indexOf() inside the loop — this is O(n^2) total and defeats the purpose.
  • Counting window size as right - left instead of right - left + 1.
  • Returning 0 for empty string — the constraints say length >= 0, so always initialize maxLen to 0.

Follow-up questions

An interviewer at AMD may pivot to one of these next:

  • Minimum Window Substring (LC 76) — find the smallest window containing all characters of t.
  • Longest Repeating Character Replacement (LC 424) — allow up to k replacements.
  • How does this pattern map to cache replacement policy analysis in a hardware prefetcher?

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

FAQ

Why check map.get(ch) >= left?

The map stores the last seen index globally. A character last seen before the current window's left boundary is no longer in the window, so it's not a duplicate for our current window.

What is the charset size for the space complexity?

For ASCII it's 128; for Unicode it could be much larger. In practice, the window size caps the Set/Map at O(n), so it's O(min(n, charset)).

Practice these live with InterviewChamp.AI

Drill Longest Substring Without Repeating Characters and other AMD interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →