Longest Substring Without Repeating Characters
Find the length of the longest run of a string in which no character appears twice. The canonical introduction to the sliding window. Solve it below in Python or JavaScript, then read the walkthrough.
Problem
You're given a string s. Return the length of the longest substring (a contiguous run of characters) in which every character is different.
Characters are case-sensitive, and spaces, digits, and symbols count as characters too.
Example 1
- Input
- s = "cabbagehead"
- Output
- 5
"bageh" has five distinct characters. Any longer run contains a repeated b, a, or e.
Example 2
- Input
- s = "zzzz"
- Output
- 1
Example 3
- Input
- s = "go to it"
- Output
- 4
Both "go t" and "o it" work. The spaces count as characters.
Constraints
- 0 ≤ s.length ≤ 5 × 10⁴
- s contains printable ASCII characters (letters, digits, symbols, and spaces).
Practice
Runs 13 tests in your browser. Python loads on the first run (about 6 MB, then cached). Press ⌘/Ctrl + Enter to run.
Get asked Longest Substring Without Repeating Characters in a real interview?
Interview Solver gives you a working solution live, during your actual coding interview. Invisible to screensharing.
How to solve Longest Substring Without Repeating Characters
Pattern: Sliding window with last-seen index
"Longest contiguous run that satisfies a condition" is the signature of a sliding window. The condition here has a useful property: if a window has no repeats, every smaller window inside it has no repeats either. That means you never have to move the left edge backward.
Grow the window by moving the right edge one character at a time. When the new character already appears inside the window, the window is broken, and the only way to fix it is to move the left edge just past that earlier copy. Everything before it can never be part of a valid window that includes the current character.
If you remember the last index where each character appeared, you can jump the left edge straight to last[ch] + 1 instead of stepping it forward one character at a time.
Approach 1: Brute force: check every substring
For each start index, extend the end one character at a time while tracking seen characters in a set, and stop at the first repeat. Record the longest length found. Each start can scan most of the string.
Time O(n · min(n, k)) where k is the alphabet size · Space O(k)
Approach 2: Sliding window with a set
Keep a set of the characters in the window. When the next character is already in the set, remove characters from the left until it isn't, then add it. Each character enters and leaves the set at most once, so this is linear, but the left edge advances one step at a time.
Time O(n) · Space O(k)
Approach 3: Sliding window that jumps
Keep last, a map from character to the most recent index where it appeared, and a left edge left = 0.
- For each index
right, ifs[right]was seen at an index≥ left, moveleftto that index + 1. - Record
last[s[right]] = right. - Update the answer with
right - left + 1.
The ≥ left check is what keeps left from moving backward when the earlier copy is already outside the window, as in "abba".
Time O(n) · Space O(k)
| Approach | Time | Space |
|---|---|---|
| Brute force: check every substring | O(n · min(n, k)) where k is the alphabet size | O(k) |
| Sliding window with a set | O(n) | O(k) |
| Sliding window that jumps | O(n) | O(k) |
Solution code
Try the practice editor first. Both solutions pass every test above.
Longest Substring Without Repeating Characters solution in Python
def length_of_longest_substring(s: str) -> int:
last: dict[str, int] = {}
left = 0
best = 0
for right, ch in enumerate(s):
if last.get(ch, -1) >= left:
left = last[ch] + 1
last[ch] = right
best = max(best, right - left + 1)
return bestLongest Substring Without Repeating Characters solution in JavaScript
function lengthOfLongestSubstring(s) {
const last = new Map();
let left = 0;
let best = 0;
for (let right = 0; right < s.length; right++) {
const ch = s[right];
if (last.has(ch) && last.get(ch) >= left) left = last.get(ch) + 1;
last.set(ch, right);
best = Math.max(best, right - left + 1);
}
return best;
}Common mistakes
- Moving the left edge to `last[ch] + 1` even when that earlier copy is already outside the window, which drags the window backward. `"abba"` should be 2, not 3.
- Returning the substring instead of its length, or the length minus one from an off-by-one in `right - left + 1`.
- Forgetting the empty string, which should return 0.
- Assuming only lowercase letters and sizing a fixed array at 26.
What interviewers look for
Name the pattern first: "this is a sliding window, because a valid window stays valid when it shrinks." Interviewers listen for that monotonic property, since it's what justifies never moving the left edge back.
Code the set version if it comes more naturally, then point out that the left edge can jump directly using last-seen indices. Trace "abba" on the whiteboard before you finish; it catches the most common bug in the jumping version.
Follow-up questions
What if at most k distinct characters are allowed instead of zero repeats?
Keep a count of each character in the window and the number of distinct characters. When the distinct count exceeds k, shrink from the left, decrementing counts until one hits zero. Still O(n).
What if you need to return the substring itself?
Store the `left` and `right` of the best window whenever you update the maximum, then slice once at the end. The cost is unchanged.
What if the alphabet is small and known, like ASCII?
Replace the hash map with a fixed array of size 128 filled with -1. Lookups get faster and memory is constant, though the complexity is the same.
Companies that ask Longest Substring Without Repeating Characters
Longest Substring Without Repeating Characters is tagged by 165 companies in our interview dataset. The score shows how often it comes up at each company.
- Walmart Labs100%
- Liberty It100%
- Turing100%
- Endava100%
- Ola100%
- Mitre100%
- Wissen Technology100%
- Freshworks100%
- Netskope100%
- Zoho97.8%
- Servicenow97.4%
- Epam Systems96.2%
- Udaan96%
- Visa95.5%
- Samcart95%
- Yelp94.2%
- Pagerduty94%
- Infosys92.8%
- Adobe91.3%
- Qualcomm90.5%
- Netflix89.7%
- Freecharge89.2%
- Blue Origin88%
- Splunk87.7%
and 141 more.
Practice next
Get live help in the real interview
Working solutions in real time during your actual interview. Invisible to screensharing.
Start Free TrialNo credit card required