Longest Substring Without Repeating Characters — Sliding Window Map
Slide a window while remembering the last index of each character so duplicates never stay in view.
Problem Statement
Return the length of the longest substring of s that contains no repeated characters.
Why This Problem Matters
- Showcases the shrinking sliding-window pattern that powers many string problems.
- Pushes you to store just enough state (last seen indices) to maintain linear time.
- Interviewers expect you to derive it quickly because the brute force is obviously too slow.
Thought Process
Establish the brute force baseline
Enumerating all substrings and checking duplicates is O(n^3) and immediately times out.
Track what breaks the window
When a duplicate arrives, the left pointer has to jump past the previous occurrence to restore validity.
Store last-seen positions
A hash map from character → last index + 1 makes updating the left pointer constant time.
Keep invariants honest
Left should only ever move forward; take the max when updating it so the window never expands backwards.
Step-by-Step Reasoning
- Initialise left = 0, maxLen = 0, and an empty map of character → index + 1.
- Walk right across the string; when s[right] was seen, move left to max(left, map.get(s[right])).
- Update maxLen with the current window length right - left + 1.
- Record map.put(s[right], right + 1) so future duplicates know where to land the left pointer.
Dry Run
s = "abcabcbb", right = 0..2
Window grows to "abc"; maxLen becomes 3 and map stores {a:1, b:2, c:3}.
Encounter second "a" at index 3
left jumps to 1, window becomes "bca", and maxLen stays 3 because duplicates never overlap.
Complexity Analysis
Time
O(n)
Space
O(k)
Why
Each character is processed once; the map stores at most k distinct characters in the alphabet.
Annotated Solution
import java.util.HashMap;
import java.util.Map;
public class LongestSubstringWithoutRepeatingCharacters {
public int lengthOfLongestSubstring(String s) {
int max = 0;
int left = 0;
Map<Character, Integer> lastSeen = new HashMap<>();
for (int right = 0; right < s.length(); right += 1) {
char c = s.charAt(right);
if (lastSeen.containsKey(c)) {
left = Math.max(left, lastSeen.get(c));
}
max = Math.max(max, right - left + 1);
lastSeen.put(c, right + 1);
}
return max;
}
}Store the previous index + 1 for every character. When a duplicate appears, the left boundary jumps forward without ever moving backward, keeping the scan linear.
Common Pitfalls
- Failing to take max when moving left can shrink the window too far and skip answers.
- Storing raw indices instead of index + 1 makes the window length off by one when duplicates appear.
- Using an array sized for ASCII fails if the input is Unicode; stick with a hash map for safety.
Follow-Up Questions
- How would you return the substring itself instead of its length?
- How do you modify the window to allow at most k replacements before a duplicate counts?