Longest Substring Without Repeating Characters
Asked at Google, Meta, Amazon, Apple, Microsoft, Netflix, Oracle, Atlassian, Rippling, Salesforce, Walmart
Problem
Given a string, find the length of the longest substring without repeating characters. This problem tests your ability to use the sliding window pattern — one of the most common techniques in FAANG coding interviews.
Asked At
| Company | Difficulty | |
|---|---|---|
| Medium | View all Google questions → | |
| Meta | Medium | View all Meta questions → |
| Amazon | Medium | View all Amazon questions → |
| Apple | Medium | View all Apple questions → |
| Microsoft | Medium | View all Microsoft questions → |
| Netflix | Medium | View all Netflix questions → |
| Oracle | Medium | View all Oracle questions → |
| Atlassian | Medium | View all Atlassian questions → |
| Rippling | Medium | View all Rippling questions → |
| Salesforce | Medium | View all Salesforce questions → |
| Walmart | Medium | View all Walmart questions → |
How to Think About It
Brute force: generate every possible substring and check if it has duplicates. That's O(n³) — n² substrings, each checked in O(n). Way too slow.
Better brute force: for each starting index, extend the ending index until you hit a duplicate. This is O(n²) with a hash set. Still not optimal.
Key insight: instead of resetting the left pointer when you find a duplicate, jump it directly to the right of the previous occurrence. A hash map storing the last seen index of each character makes this O(1).
The sliding window: maintain a window [left, right] where all characters are unique. Expand right. When you hit a duplicate at position j, move left to max(left, last_seen[j] + 1). This ensures you never check the same character twice.
Visual walkthrough for "abcabcbb":
a b c a b c b b
0 1 2 3 4 5 6 7
- window starts at left=0
- right=0: {a:0}, window="a", max=1
- right=1: {a:0,b:1}, window="ab", max=2
- right=2: {a:0,b:1,c:2}, window="abc", max=3
- right=3: a seen at 0, move left to 1. {a:3,b:1,c:2}, window="bca", max=3
- right=4: b seen at 1, move left to 2. {a:3,b:4,c:2}, window="cab", max=3
- right=5: c seen at 2, move left to 3. {a:3,b:4,c:5}, window="abc", max=3
- right=6: b seen at 4, move left to 5. {a:3,b:6,c:5}, window="cb", max=3
- right=7: b seen at 6, move left to 7. {a:3,b:7,c:5}, window="b", max=3
Result: 3 ("abc")
Optimal Approach
Use two pointers (left, right) and a hash map storing the last seen index of each character. Expand right through the string. At each character:
- If the character is in the map AND its last index >= left, it's inside the current window — a duplicate. Move left to
last_seen[char]+ 1. - Update the character's last seen index to right.
- Update max length = max(max, right - left + 1).
The condition "last_seen[char] >= left" is critical. The character might be in the map but before the current window (left already moved past it). In that case, it's not a duplicate in the current window.
Time: O(n) — each character is visited once by right. Space: O(min(n, alphabet_size)) — hash map stores at most the window size.
What Trips People Up in Real Interviews
Jumping to code without clarifying what "substring" means. A substring is contiguous — "abc" is a substring of "xabcy", but "acy" is not. If the interviewer meant subsequence, the approach changes entirely.
Resetting the left pointer to 0 when you find a duplicate. That's O(n²). The correct move is to jump left to max(left, last_seen[char] + 1). This is the optimization that makes it O(n).
Forgetting that a character's last seen index might be before the current window. If left has moved past a character's previous occurrence, it's not a duplicate in the current window. Always check last_seen[char] >= left.
Not handling the edge case of an empty string (return 0) or a single character (return 1). These seem obvious but trip people up under pressure.
Using a HashSet instead of a HashMap. A HashSet tells you IF a character exists but not WHERE it was last seen — you need the index to jump the left pointer directly instead of incrementing one by one.
Solution Code
def lengthOfLongestSubstring(s):
char_index = {}
max_len = 0
left = 0
for right, ch in enumerate(s):
if ch in char_index and char_index[ch] >= left:
left = char_index[ch] + 1
char_index[ch] = right
max_len = max(max_len, right - left + 1)
return max_lenFrequently Asked Questions
What is the Longest Substring Without Repeating Characters problem?
Given a string, find the length of the longest substring without repeating characters. This problem tests your ability to use the sliding window pattern — one of the most common techniques in FAANG coding interviews.
How do you solve Longest Substring Without Repeating Characters?
The optimal approach is described in detail above, including step-by-step walkthroughs, complexity analysis, and solution code in Python. Scroll up to the "Optimal Approach" section.
What companies ask Longest Substring Without Repeating Characters?
Longest Substring Without Repeating Characters is asked at Google, Meta, Amazon, Apple, Microsoft, Netflix, Oracle, Atlassian, Rippling, Salesforce, Walmart. It is a medium difficulty problem.
What are common mistakes on Longest Substring Without Repeating Characters?
- Jumping to code without clarifying what "substring" means. A substring is contiguous — "abc" is a substring of "xabcy", but "acy" is not. If the interviewer meant subsequence, the approach changes entirely.
- Resetting the left pointer to 0 when you find a duplicate. That's `O(n²)`. The correct move is to jump left to max(left, `last_seen[char]` + 1). This is the optimization that makes it `O(n)`.
- Forgetting that a character's last seen index might be before the current window. If left has moved past a character's previous occurrence, it's not a duplicate in the current window. Always check `last_seen[char]` >= left.
- Not handling the edge case of an empty string (return 0) or a single character (return 1). These seem obvious but trip people up under pressure.
- Using a `HashSet` instead of a `HashMap`. A `HashSet` tells you IF a character exists but not WHERE it was last seen — you need the index to jump the left pointer directly instead of incrementing one by one.