16. Longest Substring Without Repeating Characters

mediumAsked at ServiceNow

Find the length of the longest substring with all unique characters using a sliding window. ServiceNow asks this to assess hash-map + two-pointer fluency — the same pattern underpins their duplicate-detection logic in event correlation pipelines.

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

Source citations

Public interview reports confirming this problem appears in ServiceNow loops.

LeetCode Discuss (2026)— Listed by candidates as a common ServiceNow technical screen question.
Glassdoor (2025)— Reported in ServiceNow SDE-I onsite coding round.

Problem

Given a string s, find the length of the longest substring without repeating characters. A substring is a contiguous non-empty sequence of characters within a string.

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', with length 1.

Approaches

1. Brute force: check all substrings

Enumerate every pair (i, j), verify uniqueness via a set, track max length.

Time: O(n^2)
Space: O(min(n, charset))

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

Tradeoff: O(n^2) — unusable on ServiceNow's log-stream volumes. Reinitializes a set on every outer iteration, which is also allocation-heavy.

2. Sliding window with last-seen map

Maintain a window [left, right]. Store the last seen index of each character. When a repeat is found, jump left past the previous occurrence rather than shrinking one step at a time. This amortizes to O(n) because each character is processed at most twice.

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

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

Tradeoff: O(n) time, O(charset) space — optimal. The guard `lastSeen.get(ch) >= left` is critical: it prevents jumping left backwards when a character was last seen before the current window started.

ServiceNow-specific tips

ServiceNow interviewers specifically look for the `>= left` guard on the map lookup — it separates candidates who truly understand the invariant from those who memorized the sliding-window template. Mention that in a ServiceNow event-correlation context, this pattern detects the longest sequence of unique event types in a rolling time window.

Common mistakes

Omitting the `lastSeen.get(ch) >= left` guard — causes left to jump backwards, which destroys the window invariant.
Tracking window size as right - left instead of right - left + 1 — off-by-one that affects every window size.
Using a Set and doing set.delete(s[left++]) instead of the map jump — correct but O(n^2) worst-case on repeated characters.

Follow-up questions

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

Longest substring with at most K distinct characters (LC 340).
Minimum window substring containing all characters of t (LC 76).
Find all anagrams of p in s (LC 438).

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 store last-seen index instead of a boolean set?

Storing the index lets you jump left directly to one past the duplicate, skipping many characters in one step. A boolean set would require shrinking left one position at a time, making worst-case O(n^2).

What if the string has Unicode characters?

A Map handles any character key, so no code change needed. If you used a fixed-size array indexed by char code, you'd need to know the charset size upfront — mention this to show you think about character encoding.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →