Find longest unique-character substring
Company: Snowflake
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
Given a string s, return the length of the longest substring without repeating characters. Explain and implement an O(n) sliding-window solution using a hash map or set. Discuss time and space complexity, and note any changes needed to correctly handle Unicode characters.
Quick Answer: This question evaluates proficiency in string manipulation, use of associative data structures (hash maps/sets), and algorithmic thinking for detecting and maintaining unique-character substrings.
Given a string `s`, return the length of the longest substring of `s` that contains no repeating characters.
A substring is a contiguous run of characters within the string. Implement an O(n) sliding-window solution using a hash map (character -> last seen index) or a set. As the right edge of the window expands one character at a time, advance the left edge just past the previous occurrence of any character that would otherwise repeat, and track the maximum window width seen.
Note on Unicode: iterating in Python over `str` already yields Unicode code points, so the algorithm is correct as written for the basic multilingual characters most inputs use. For full correctness over user-perceived characters (grapheme clusters such as emoji with combining marks or skin-tone modifiers), you would segment on grapheme boundaries rather than code points before applying the same window logic.
Return 0 for an empty string.
Constraints
- 0 <= len(s) <= 5 * 10^4
- s may contain letters, digits, symbols, and spaces (any Unicode code points)
- Return 0 for the empty string
Examples
Input: ("abcabcbb",)
Expected Output: 3
Explanation: The answer is "abc", length 3.
Input: ("bbbbb",)
Expected Output: 1
Explanation: The answer is "b", length 1 — every character repeats.
Hints
- Use two pointers forming a window [start, i]; expand i one step at a time and shrink from the left only when you hit a repeat.
- Store the last index at which each character was seen so you can jump start directly past the previous occurrence instead of stepping one-by-one.
- Guard the jump with `last_seen[ch] >= start` — a stale occurrence that is already outside the window (e.g. the second 'a' in "abba") must not move start backward.