3. Longest Substring Without Repeating Characters

mediumAsked at Shopify

Shopify uses this to test sliding-window mastery. Whether the candidate uses Set vs Map for state and whether they advance the left pointer correctly are the two grading bars.

By Alex Chen, Founder, InterviewChamp.AI · Last verified 2026-05-19

Source citations

Public interview reports confirming this problem appears in Shopify loops.

Glassdoor (2026-Q1)— Shopify Backend Developer + Production Engineer phone screens cite this as a recurring medium-round question.
Reddit r/cscareerquestions (2025-11)— Shopify new-grad reports include this as a 25-minute coding round.

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

Explanation: The answer is "abc", with length 3.

Example 2

Input

s = "bbbbb"

Output

Explanation: The answer is "b".

Example 3

Input

s = "pwwkew"

Output

Explanation: The answer is "wke".

Approaches

1. Brute-force enumerate substrings

For each (i, j) pair, check whether the substring s[i..j] has all unique characters. Track the max length.

Time: O(n^3)
Space: O(min(n, alphabet))

function lengthBrute(s) {
  let best = 0;
  for (let i = 0; i < s.length; i++) {
    for (let j = i; j < s.length; j++) {
      const seen = new Set();
      let ok = true;
      for (let k = i; k <= j; k++) {
        if (seen.has(s[k])) { ok = false; break; }
        seen.add(s[k]);
      }
      if (ok) best = Math.max(best, j - i + 1);
    }
  }
  return best;
}

Tradeoff: Cubic. n = 50000 means 10^14 ops — won't finish. Mention it only as the naive baseline.

2. Sliding window with Set

Expand the right pointer; when a duplicate appears, shrink from the left until the duplicate is removed. Track max window size.

Time: O(n)
Space: O(min(n, alphabet))

function lengthOfLongestSubstring(s) {
  const seen = new Set();
  let left = 0;
  let best = 0;
  for (let right = 0; right < s.length; right++) {
    while (seen.has(s[right])) {
      seen.delete(s[left]);
      left++;
    }
    seen.add(s[right]);
    best = Math.max(best, right - left + 1);
  }
  return best;
}

Tradeoff: Each character is added and removed from the set at most once -> O(n). Clean, idiomatic, and what most Shopify candidates write.

3. Sliding window with Map (jump on duplicate)

Store each character's last seen index. On duplicate, jump left to max(left, lastSeen[ch] + 1) instead of shrinking one step at a time.

Time: O(n)
Space: O(min(n, alphabet))

function lengthOfLongestSubstringMap(s) {
  const lastSeen = new Map();
  let left = 0;
  let best = 0;
  for (let right = 0; right < s.length; right++) {
    const ch = s[right];
    if (lastSeen.has(ch) && lastSeen.get(ch) >= left) {
      left = lastSeen.get(ch) + 1;
    }
    lastSeen.set(ch, right);
    best = Math.max(best, right - left + 1);
  }
  return best;
}

Tradeoff: Single-pass, no inner while. Same asymptotic complexity but fewer operations in practice. The Map version is the one Shopify senior interviewers nudge candidates toward.

Shopify-specific tips

Shopify interviewers grade this on whether you reach for sliding window without prompting. After you ship the Set version, expect 'can you do it without the inner while loop?' — that's the cue to switch to the Map version with index-jump. Volunteer both if you have time; it shows you understand that both achieve O(n) but the Map version is structurally cleaner.

Common mistakes

Forgetting to compare `lastSeen.get(ch) >= left` in the Map version — without it, you'd jump left BACKWARDS when an old duplicate appears outside the current window.
Using right - left instead of right - left + 1 for the window size.
Resetting the set on each new starting position (that's the brute force, not sliding window).
Iterating the string with for..of and trying to use the index — for..of doesn't give you the index.

Follow-up questions

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

Longest substring with at most K distinct characters (LeetCode 340).
Longest substring with exactly K distinct characters.
Same problem but on a stream — bounded memory.
Return the actual substring, not just its length.
Generalize to find the longest subarray of integers with no duplicates.

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 O(n), not O(n^2), for the Set version?

Both pointers only ever move right. Each character is added to the set at most once and removed at most once, so the total work is 2n across the whole run, not n per iteration.

Set vs Map — which one is canonical?

Both achieve O(n). Set is shorter to write; Map is slightly faster in practice because the index-jump avoids the inner while. Shopify accepts either; the Map version scores higher on the 'I know multiple sliding-window flavors' axis.

Free learning resources

Curated free links for this problem.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →