Quick Overview

Implement the length of the longest contiguous substring whose ASCII characters are all distinct. Focus on contiguous-range reasoning, repeated-character boundaries, empty inputs, case sensitivity, and linear-time scalability for long strings.

Find the Longest Substring Without Repeated Characters

Company: Netflix

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

## Find the Longest Substring Without Repeated Characters ### Problem Implement `longestUniqueSubstringLength(text) -> length`. Return the length of the longest contiguous substring in which every character is distinct. Return only the length, not the substring. ### Portable Contract - `text` is an ASCII string and character comparison is exact and case-sensitive. - `0 <= text.length <= 200,000` ASCII characters. - An empty string returns `0`. - The input must not be modified. - Target `O(text.length)` time and `O(1)` auxiliary space for the fixed ASCII alphabet. A solution that repeatedly rescans the active window does not meet the time target. ```hint Remember the last position When a repeated character appears, its most recent index can move the left boundary directly instead of removing characters one at a time. ``` ### Examples ```text text = "abcabcbb" length = 3 ``` ```text text = "abba" length = 2 ``` ```text text = "" length = 0 ``` ### Discussion Requirements - State the invariant maintained by the left and right boundaries. - Explain why the left boundary must never move backward when a character last seen before the current window repeats. - Compare a set-based sliding window with a last-index map and describe which operations each performs. - Include tests with adjacent repeats, a repeat after the previous copy has left the window, and case-distinct characters.

Quick Answer: Implement the length of the longest contiguous substring whose ASCII characters are all distinct. Focus on contiguous-range reasoning, repeated-character boundaries, empty inputs, case sensitivity, and linear-time scalability for long strings.

Implement `longestUniqueSubstringLength(text)`. Given an ASCII string `text`, return the length of the longest contiguous substring of `text` in which every character is distinct. Return only the length, never the substring itself. ### Output semantics - The return value is a single non-negative integer: the number of characters in the longest contiguous all-distinct substring of `text`. - The answer is unique for every input. Several different substrings may attain the maximum length, but they all have the same length, so no tie-breaking or ordering rule is needed. - An empty string returns `0`. - Character comparison is exact and case-sensitive: `'a'` and `'A'` are two different characters, and one substring may contain both. - `text` is an ASCII string, which means every character has a code point in the inclusive range `0` through `127`. All 128 of those code points are legal input. Control characters -- NUL (`0x00`), backspace (`0x08`), tab (`0x09`), line feed (`0x0a`), form feed (`0x0c`), carriage return (`0x0d`) -- and DEL (`0x7f`) are ordinary characters here: they are compared like any other character and may appear inside the winning substring. Because the alphabet holds 128 distinct symbols, the answer never exceeds `min(len(text), 128)`. - `text` must not be modified: do not trim, case-fold, or normalize it. ### Examples Example 1 ```text text = "abcabcbb" returns 3 ``` The longest contiguous all-distinct substring is `"abc"`, of length 3. Every substring of length 4 or more repeats a character. Example 2 ```text text = "abba" returns 2 ``` `"ab"` (indices 0-1) and `"ba"` (indices 2-3) are both all-distinct and have length 2. Reading the second `'b'` at index 2 forces the window to start at index 2. Reading the final `'a'` at index 3 must NOT pull the window start back to index 1: the earlier `'a'` at index 0 has already left the window, so the window start stays at index 2 and the window is `"ba"`. Example 3 ```text text = "" returns 0 ``` ### Performance Target `O(len(text))` time and `O(1)` auxiliary space for the fixed 128-symbol ASCII alphabet. A solution that repeatedly rescans the active window does not meet the time target.

Constraints

  • 0 <= len(text) <= 200,000
  • Every character of text is an ASCII character: 0 <= ord(character) <= 127. All 128 code points are legal input, including NUL (0x00), backspace (0x08), tab (0x09), line feed (0x0a), form feed (0x0c), carriage return (0x0d) and DEL (0x7f).
  • Character comparison is exact and case-sensitive.
  • The returned length is an integer with 0 <= length <= min(len(text), 128); 128 is the size of the ASCII alphabet, so no intermediate value or result ever approaches a 32-bit limit.
  • An empty string returns 0.
  • text must not be modified.
  • Target O(len(text)) time and O(1) auxiliary space for the fixed 128-symbol ASCII alphabet; repeatedly rescanning the active window does not meet the time target.

Examples

Input: ('',)

Expected Output: 0

Input: ('a',)

Expected Output: 1

Hints

  1. Maintain a window text[left..right] whose characters are always distinct. The only decision at each step is where left has to move when text[right] is already inside the window.
  2. One slot per ASCII code point (128 entries) holding the most recent index of each character lets left jump in a single step instead of walking forward one character at a time. Index that table by the raw code point -- code points below 0x20 and DEL are legal input, so an offset from a printable base is out of bounds.
  3. A character can repeat long after its earlier copy has fallen out of the window. Compare the stored index against the current left before you trust it.

Loading coding console...