Skip to main content

12. Longest Substring Without Repeating Characters

mediumAsked at Freshworks

Find the longest run of unique characters in a string — Freshworks frames it as the longest stretch of distinct tags on a ticket timeline before a rule re-fires.

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

Problem

Given a string s, return the length of the longest substring without duplicate 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" has length 3

Example 2

Input
s = "bbbbb"
Output
1

Approaches

1. Brute force

Try every substring; check uniqueness with a Set.

Time
O(n^3)
Space
O(n)
let best=0;
for (let i=0;i<s.length;i++)
  for (let j=i;j<s.length;j++) {
    const sub=s.slice(i,j+1);
    if (new Set(sub).size === sub.length) best=Math.max(best,sub.length);
  }
return best;

Tradeoff:

2. Sliding window with last-seen map

Slide a window [l, r]. On each char, if we've seen it inside the window, jump l past the prior occurrence. Track the best length.

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

Tradeoff:

Freshworks-specific tips

Freshworks pushes for the last-seen-index variant, not the shrink-by-one window — they want you to demonstrate you can jump the left pointer instead of marching it.

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 Freshworks interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →