Implement Python Function for Longest Unique Substring Length
Company: Amazon
Role: Data Scientist
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
##### Scenario
Real-time text analytics service enforcing uniqueness constraints
##### Question
Implement a Python function returning the length of the longest substring without repeating characters. Follow-up: modify it to return all substrings that meet this criterion.
##### Hints
Sliding window with hash map for indices; for follow-up, track start positions and collect substrings of max length.
Quick Answer: This question evaluates string manipulation and algorithmic problem-solving skills by requiring a Python implementation to determine the length of the longest substring without repeating characters, with an optional follow-up to extract all maximal substrings.
Longest Substring Without Repeating Characters — Length
You are building a real-time text analytics service that enforces a uniqueness constraint on character windows. Given a string `s`, return the length of the longest substring of `s` that contains no repeating characters.
A substring is a contiguous sequence of characters within the string. The answer is the maximum window length you can slide over `s` such that every character inside the window is distinct.
Examples:
- `"abcabcbb"` -> `3` (the answer is `"abc"`).
- `"bbbbb"` -> `1` (the answer is `"b"`).
- `"pwwkew"` -> `3` (the answer is `"wke"`; note `"pwke"` is a subsequence, not a substring).
- `""` -> `0`.
Use a sliding window with a hash map from each character to its most recent index. When you encounter a repeat that lies inside the current window, jump the window start to one past the previous occurrence. Track the maximum window length as you go.
Constraints
- 0 <= len(s) <= 5 * 10^4
- s consists of English letters, digits, symbols, and spaces.
- The empty string has answer 0.
- Substrings must be contiguous (not subsequences).
Examples
Input: ("abcabcbb",)
Expected Output: 3
Explanation: The longest substring without repeats is "abc", length 3.
Input: ("bbbbb",)
Expected Output: 1
Explanation: Every character is the same; the best window is a single "b".
Hints
- Maintain a sliding window [start, i] that always contains distinct characters.
- Store the most recent index of each character in a hash map.
- When the current character was last seen at index j >= start, move start to j + 1 instead of shrinking one step at a time.
- After updating the window for index i, the current length is i - start + 1; keep the running maximum.
Longest Substring Without Repeating Characters — All Maximal Substrings
Follow-up to the length problem. Given a string `s`, return every distinct substring of `s` that has no repeating characters AND whose length equals the maximum such length. Return the substrings as a list sorted in ascending lexicographic order, with duplicates removed.
For example, in `"abcabcbb"` the maximum length is 3 and the maximal windows are `"abc"`, `"bca"`, and `"cab"`, so the answer is `["abc", "bca", "cab"]`. For `"pwwkew"` the maximum length is 3 and both `"wke"` and `"kew"` qualify, giving `["kew", "wke"]` after sorting. For the empty string return `[]`.
Extend the sliding-window approach: track the maximum length found so far, and collect the window text each time you hit that length. When you find a strictly longer window, discard the old collection and start fresh. Finally de-duplicate (the same substring text can occur at multiple positions) and sort.
Constraints
- 0 <= len(s) <= 5 * 10^4
- s consists of English letters, digits, symbols, and spaces.
- Return distinct substrings only (the same text appearing at different positions counts once).
- Output is sorted in ascending lexicographic order.
- For the empty string return an empty list.
Examples
Input: ("abcabcbb",)
Expected Output: ["abc", "bca", "cab"]
Explanation: Max length is 3; the three distinct length-3 windows are abc, bca, cab.
Input: ("bbbbb",)
Expected Output: ["b"]
Explanation: Max length is 1 and the only distinct window is "b".
Hints
- Run the same sliding window as the length problem, but also remember the window text whenever its length ties the current maximum.
- When you find a strictly longer window, reset your collection to just that new window.
- The same substring text can appear at multiple start positions, so de-duplicate with a set before returning.
- Sort the final list so the output is deterministic regardless of scan order.