3. Longest Substring Without Repeating Characters
Model: qwen3.5:9b
Topics: Hash Table,Two Pointers,String,Sliding Window
FAANG asked: 1
Acceptance rate: 31.5%
Problem Breakdown
We need to find the maximum length of a contiguous substring where every character is unique (no duplicates allowed within that specific window).
- Input: A string
scontaining letters, digits, symbols. Length up to 50k. - Output: An integer representing the max length found.
- Edge Cases: Empty string (
"") should return 0. Strings with all identical characters (e.g., “bbbbb”) should return 1. Subsequences are not allowed; order and contiguity matter.
Intuition
A naive brute-force approach would iterate through every possible substring, check for duplicates in each one using a set or sorting, and track the max length. This results in O(N^3) time complexity because there are N*(N+1)/2 substrings, and checking uniqueness takes linear time relative to window size.
We can optimize this by observing that as we expand our right pointer (right), if we encounter a character already present in our current valid window, the new substring cannot start before or at the previous occurrence of that duplicate character.
Instead of resetting left all the way back to 0 every time, we only need to move left past the last seen index of the repeating character. This suggests an O(N) solution using a Sliding Window pattern combined with a Hash Map (dictionary in Python) to store the most recent index of each character encountered so far.
Approach
- Initialize two pointers:
left = 0, and trackmax_len. - Use a dictionary (
char_map) to store the last seen index for every unique character. - Iterate with
rightfrom 0 to length-1:- Check if current char
s[right]is in our map AND its stored index is >=left. This means it’s inside our current window (a duplicate). - If a valid duplicate exists, move
lefttochar_map[s[right]] + 1. We discard the substring up to and including that previous occurrence. - Update
max_len = max(max_len, right - left + 1). - Always update the map with the current index of
s[right], even if it was a duplicate (to track its new position).
- Check if current char
Complexity Analysis
- Time: O(N), where N is length of string. We traverse the string once; dictionary operations are amortized O(1). The left pointer moves forward at most as many times as the right pointer, so total movements for both pointers combined is 2N.
- Space: O(min(M, K)), where M is alphabet size (ASCII/Unicode) and K is number of unique characters in
s. In practice bounded by constant space if charset is fixed, or proportional to string length otherwise.
Solution
def lengthOfLongestSubstring(s: str) -> int:
char_map = {} # Stores last index of each character
left = 0 # Left pointer for sliding window
max_len = 0
for right, char in enumerate(s):
if char in char_map and char_map[char] >= left:
# Duplicate found within current window.
# Move left past the previous occurrence of this character.
left = char_map[char] + 1
# Update last seen index to current position for future checks
char_map[char] = right
# Calculate current valid substring length and update max_len
max_len = max(max_len, right - left + 1)
return max_len
Edge Cases Handled
- Empty String: Loop does not execute;
max_lenremains initialized to 0. Correctly returns 0. - All Duplicates (e.g., “bbbbb”): On second ‘b’,
leftjumps past the first index, window size becomes 1 repeatedly. Returns 1. - No Duplicates:
char_mapcheck fails every time;max_lengrows to full string length N. - Duplicate at End of String: Logic correctly updates map and calculates final valid substring ending before or including current char depending on previous duplicates.