Skip to main content

3. Longest Substring Without Repeating Characters

mediumAsked at HP

HP's document-processing and OCR pipelines apply sliding-window algorithms for character-sequence analysis in scanned text streams. This problem is a textbook sliding-window exercise — HP uses it to confirm that candidates can translate a brute-force nested loop into an O(n) single-pass scan.

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

Source citations

Public interview reports confirming this problem appears in HP loops.

  • Glassdoor (2026-Q1)— HP software engineer onsite feedback mentions this problem in multiple second-round reports.
  • Blind (2025-11)— Listed in HP SWE interview prep threads as a sliding-window problem that frequently appears in technical screens.

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: The answer is 'abc', with the length of 3.

Example 2

Input
s = "bbbbb"
Output
1

Explanation: The answer is 'b', with the length of 1.

Example 3

Input
s = "pwwkew"
Output
3

Explanation: The answer is 'wke', with the length of 3.

Approaches

1. Sliding window with set

Maintain a window [left, right]. Expand right; when a repeat is found, shrink from left until the duplicate is removed. Track the maximum window size.

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

Tradeoff: O(n) time, clean window management. Each character is added and removed at most once, giving amortized O(1) per character.

2. Sliding window with index map (optimized jump)

Store the last seen index of each character. When a repeat is found, jump left directly to lastSeen[char] + 1 instead of shrinking one step at a time.

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

Tradeoff: Same O(n) complexity but avoids the inner while loop — left jumps directly to the correct position. Slightly faster in practice and preferred by experienced interviewers.

HP-specific tips

HP interviewers appreciate the progression from brute force → set-based window → map-based jump. Present the map-based approach as the production version because it eliminates the inner while loop. Make sure to explain the guard condition lastSeen.get(s[right]) >= left — without it, a character seen before the current window incorrectly contracts the window.

Common mistakes

  • Shrinking the window by one step at a time when an index map can jump directly — works but is slower by a constant factor.
  • Missing the >= left guard in the index-map version — a stale entry from outside the current window should not shrink left.
  • Not initializing left = 0 before the loop and using it inconsistently.
  • Counting window size as right - left instead of right - left + 1 — off-by-one error.

Follow-up questions

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

  • What if you need to find the actual substring, not just its length?
  • Longest Substring with At Most Two Distinct Characters (LC 159).
  • How does the algorithm change if the input is a stream of characters arriving one at a time?

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 does the index-map need the >= left check?

lastSeen stores the most recent index of a character globally. If that index is to the left of our current window (< left), the character is no longer in the window and doesn't cause a conflict.

What is the space complexity for an ASCII string?

At most 128 distinct ASCII characters, so O(128) = O(1) effectively. For Unicode the bound is O(min(n, 65536)).

Does the order of operations matter — update lastSeen before or after checking?

Check first, then update. If you update lastSeen before checking, you overwrite the old index and lose the duplicate detection.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →