MediumHash TableStringSliding WindowUpdated Sep 2026

3. Longest Substring Without Repeating Characters

Asked at Google, Meta, Amazon, Apple and 13 more

Difficulty

Medium

Time

O(n)

Space

O(min(n, k))

Pattern

Hash Table

Companies

17

Problem

Given a string, find the length of the longest run of characters that contains no repeats.

The run has to be a substring — the characters must sit next to each other in the original string. Picking characters from here and there (a subsequence) does not count.

What counts as an answer

length 3abcabcbb01234567"abc" — no character repeats inside it
Only unbroken stretches count. The best stretch in "abcabcbb" has length 3.

Constraints

  • ●0 <= s.length <= 10^5
  • ●s can contain letters, digits, symbols and spaces

Examples

Example 1
Inputs = "abcabcbb"
Output3
WhyThe longest run with no repeats is "abc". "bca" and "cab" are equally good answers of the same length.
Example 2
Inputs = "bbbbb"
Output1
WhyEvery character is the same, so the best you can do is a single "b".
Example 3
Inputs = "pwwkew"
Output3
WhyThe answer is "wke". "pwke" is longer but its characters are not next to each other, so it does not count.

Asked At

17 companies
CompanyDifficulty
GoogleMediumView all Google questions →
MetaMediumView all Meta questions →
AmazonMediumView all Amazon questions →
AppleMediumView all Apple questions →
MicrosoftMediumView all Microsoft questions →
NetflixMediumView all Netflix questions →
OracleMediumView all Oracle questions →
AtlassianMediumView all Atlassian questions →
RipplingMediumView all Rippling questions →
SalesforceMediumView all Salesforce questions →
WalmartMediumView all Walmart questions →
BloombergMediumView all Bloomberg questions →
Goldman SachsMediumView all Goldman Sachs questions →
LinkedInMediumView all LinkedIn questions →
VisaMediumView all Visa questions →
NVIDIAMediumView all NVIDIA questions →
JPMorganMediumView all JPMorgan questions →

How to Think About It

1

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.

2

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.

3

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).

4

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.

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:

  1. 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.
  2. Update the character's last seen index to right.
  3. 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.

Sliding window

window = 3abcabcbb01234567leftrightStep 1 — grow right while everything inside is uniquewindow = 3abcabcbb01234567leftrightStep 2 — 'a' repeats, so left jumps just past the old 'a'best = max(best, right − left + 1)answer stays 3
right always moves forward. left only jumps when the new character is already inside the window.
ComplexityTime O(n)Space O(min(n, k))Each character is visited at most twice — once by right, once by left. k is the alphabet size.

What Trips People Up in Real Interviews

1

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.

2

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).

3

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.

4

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.

5

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

O(n) time
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_len

Pro at DSA?

Test your skills with a real FAANG-style mock interview.

Start a Mock Interview →

Frequently 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 runs in O(n) time and O(min(n, k)) space. Scroll up to "Optimal Approach" for the step-by-step walkthrough, diagrams, and code in Python, C++ and Java.

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, Bloomberg, Goldman Sachs, LinkedIn, Visa, NVIDIA, JPMorgan. 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.