Skip to main content

15. Longest Substring Without Repeating Characters

mediumAsked at Coupang

Find the longest substring without repeats, mirroring how Coupang's Korean e-commerce search ranking computes max-distinct windows over user query history.

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

Problem

Given a string s, return 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

Example 2

Input
s="pwwkew"
Output
3

Approaches

1. Brute force

Try every substring and check uniqueness.

Time
O(n^3)
Space
O(n)
for each (i, j) check Set(s.slice(i,j)).size === j-i;
track max length;

Tradeoff:

2. Sliding window with last-seen map

Slide a right pointer; on a repeat, jump the left pointer past the prior occurrence.

Time
O(n)
Space
O(min(n, alphabet))
function lengthOfLongestSubstring(s) {
  const last = new Map();
  let best = 0, left = 0;
  for (let r = 0; r < s.length; r++) {
    if (last.has(s[r]) && last.get(s[r]) >= left) {
      left = last.get(s[r]) + 1;
    }
    last.set(s[r], r);
    best = Math.max(best, r - left + 1);
  }
  return best;
}

Tradeoff:

Coupang-specific tips

Coupang's Korean e-commerce search ranking computes max-distinct windows over recent query streams; sliding-window with last-seen map is the canonical pattern in their query-log analytics.

Solve it now

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

Output

Press Run or Cmd+Enter to execute

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →