#3 Longest Substring Without Repeating Characters
frequently reported atWalmartInfosysAdobeNetflixByteDance / TikTokBloomberg
the problem
In plain words
Return the length of the longest substring of s in which no character repeats.
in s = "abcabcbb"
out 3
"abc".
in s = "bbbbb"
out 1
in s = "pwwkew"
out 3
"wke". "pwke" is a subsequence, not a substring.
- 0 ≤ s.length ≤ 5·10⁴
- English letters, digits, symbols and spaces
your turn
Try it before you peek
Read the examples, say the brute force out loud, then write code: here or on LeetCode ↗. Stuck for 20 minutes? Open one hint at a time.
Solve it in the browser
LeetCode-style: complete the class. Compiled by the real javac (Java 17) and judged right here — nothing is sent anywhere.
Solutions are hidden so you can try first. Even 20 minutes of real effort makes the answer stick far better than reading it.
Marking the problem solved, or opening every hint, also shows it.
the aha
Key insight
patternSliding window (variable size)
If s[left..right] has a duplicate, every longer window that contains it has the same duplicate. So when a repeat enters, move left past the earlier copy — never back.
solutions
From brute force to optimal
Try all (i, j) pairs and test each substring for uniqueness with a set.
- For each i, for each j ≥ i, check s[i..j] with a fresh HashSet.
- Track the longest unique one.
About n²/2 substrings, each checked in O(n).
The set holds at most one copy of each character (σ = alphabet size).
class Solution { public int lengthOfLongestSubstring(String s) { int best = 0; for (int i = 0; i < s.length(); i++) { for (int j = i; j < s.length(); j++) { if (allUnique(s, i, j)) best = Math.max(best, j - i + 1); } } return best; } private boolean allUnique(String s, int from, int to) { Set<Character> seen = new HashSet<>(); for (int i = from; i <= to; i++) { if (!seen.add(s.charAt(i))) return false; // add() returns false on a repeat } return true; }}From every start, keep extending until the first repeat — no need to re-check from scratch.
- For each i: new set; extend j while s[j] is not in the set.
- The run length when it stops is the best for that start.
Each start extends at most σ + 1 characters before a repeat is forced.
One set at a time.
class Solution { public int lengthOfLongestSubstring(String s) { int best = 0; for (int i = 0; i < s.length(); i++) { Set<Character> seen = new HashSet<>(); for (int j = i; j < s.length() && seen.add(s.charAt(j)); j++) { best = Math.max(best, j - i + 1); // stops at the first repeat } } return best; }}Grow right; if the new char is duplicated, shrink left until it is unique again.
- count = int[128]; left = 0.
- For each right: count[c]++.
- While count[c] > 1: count[s[left]]--, left++.
- best = max(best, right − left + 1).
Each character enters once and leaves at most once.
A fixed 128-slot array.
class Solution { public int lengthOfLongestSubstring(String s) { int[] count = new int[128]; // ASCII counts for the window int left = 0, best = 0; for (int right = 0; right < s.length(); right++) { char c = s.charAt(right); count[c]++; while (count[c] > 1) { // c is now duplicated count[s.charAt(left)]--; left++; } best = Math.max(best, right - left + 1); } return best; }}Dry run
Remember where each char was last seen; on a repeat, jump left straight past it.
- last = HashMap<char, index>.
- If c was seen at prev ≥ left, set left = prev + 1.
- Update last[c] = right and the best length.
One pass; left jumps instead of stepping, but the bound is the same.
One entry per distinct character.
class Solution { public int lengthOfLongestSubstring(String s) { Map<Character, Integer> last = new HashMap<>(); // char -> last index seen int left = 0, best = 0; for (int right = 0; right < s.length(); right++) { char c = s.charAt(right); Integer prev = last.get(c); if (prev != null && prev >= left) left = prev + 1; // jump past the old copy last.put(c, right); best = Math.max(best, right - left + 1); } return best; }}in the room
How to say it in the interview
talk track
- Clarify the character set — it decides between
int[128]and a HashMap. - State the window rule: "the window never contains a duplicate". The rest follows from it.
- For the jump version, explain the
prev >= leftcheck with "abba": the old 'a' is already outside the window.
traps
- Jump version without
prev >= left: on "abba",leftwould jump backwards to 1. - Confusing substring (contiguous) with subsequence.
what they ask next
Follow-ups
Longest substring with at most k distinct characters (LC 340)?
Same window; state = HashMap of counts; shrink while map.size() > k.
Longest substring with at most two distinct characters (LC 159)?
LC 340 with k = 2.
before you submit
Edge cases to test
- Empty string → 0.
- The same character repeated ("bbbbb") → 1.
- "abba": a jump-based
leftmust never move backwards — checkprev >= left. - Spaces, digits and symbols are characters too: use
int[128], notint[26].
practise next
Similar problems
- #424Longest Repeating Character ReplacementMediumin Sliding Window
- #1004Max Consecutive Ones IIIMediumin Sliding Window
- #219Contains Duplicate IIEasyin Sliding Window