A complete visual walkthrough of the sliding window technique — from brute force to an elegant O(n) solution.
Given a string s, find the length of the longest substring without duplicate characters.
Example 1:
Input: s = "abcabcbb" Output: 3 Explanation: The answer is "abc", with the length of 3. Note that"bca"and"cab"are also correct answers.
Example 2:
Input: s = "bbbbb" Output: 1 Explanation: The answer is "b", with the length of 1.
Example 3:
Input: s = "pwwkew" Output: 3 Explanation: The answer is "wke", with the length of 3. Notice that the answer must be a substring, "pwke" is a subsequence and not a substring.
Constraints:
0 <= s.length <= 5 * 104s consists of English letters, digits, symbols and spaces.The simplest idea: check every possible substring, and for each one, verify it has no repeating characters using a Set. Track the longest valid one.
We must check O(n2) substrings, and verifying each takes O(n) time in the worst case, giving O(n3) overall. With a Set we can verify in O(1) amortized per character, bringing it to O(n2).
The problem: We throw away useful information. When we find "abc" is valid and "abca" is not (because 'a' repeats), we start over from 'b'. But we already know "bca" is valid from the previous check! Can we reuse that knowledge?
Instead of restarting from scratch, maintain a window [left, right] that always contains unique characters. Expand right to grow the window. When a duplicate is found, jump left past the previous occurrence.
Use a HashMap to remember the last seen index of each character. When character c at index right was last seen at index k and k >= left, jump left to k + 1.
left past the previous occurrence. The window shrinks but stays valid.maxLen = max(maxLen, right - left + 1).Why HashMap over Set? A Set tells us whether a character is in the window, but to shrink correctly we would need to remove characters one by one from the left. A HashMap storing the last index lets us jump left directly to the right position in O(1) — no incremental removals needed.
Let's trace through "abcabcbb" step by step. The blue bracket shows the current window [left..right]. The amber cell is the character being examined.
Notice how left only moves forward — it never backtracks. Both left and right traverse the string at most once, giving us a single pass through the data. The map.get(c) >= left check is critical: it ignores stale entries from characters that are already outside the window.
Let's verify the algorithm handles tricky inputs correctly.
The map.get(c) >= left guard is especially important when a character appears in the map but is already outside the current window (its stored index is less than left). Without this check, we would incorrectly shrink the window. For example, in "abba" when processing the final 'a', the map says 'a' was at index 0 but left is already at 2 — so index 0 is outside the window and should be ignored.
class Solution { public int lengthOfLongestSubstring(String s) { // Map each character to the index where it was last seen Map<Character, Integer> map = new HashMap<>(); int maxLen = 0; // tracks our best answer int left = 0; // left boundary of the window for (int right = 0; right < s.length(); right++) { char c = s.charAt(right); // If c was seen before AND its last position is // within [left..right), the window contains a duplicate if (map.containsKey(c) && map.get(c) >= left) { // Shrink window: move left past the previous occurrence left = map.get(c) + 1; } // Record / update the position of character c map.put(c, right); // Update the maximum window length seen so far maxLen = Math.max(maxLen, right - left + 1); } return maxLen; } }
func lengthOfLongestSubstring(s string) int { // Map each character to the index where it was last seen lastSeen := make(map[byte]int) maxLen := 0 // tracks our best answer left := 0 // left boundary of the window for right := 0; right < len(s); right++ { c := s[right] // If c was seen before AND its last position is // within [left..right), the window contains a duplicate if idx, ok := lastSeen[c]; ok && idx >= left { // Shrink window: move left past the previous occurrence left = idx + 1 } // Record / update the position of character c lastSeen[c] = right // Update the maximum window length seen so far if right-left+1 > maxLen { maxLen = right - left + 1 } } return maxLen }
def length_of_longest_substring(s: str) -> int: # Map each character to the index where it was last seen last_seen: dict[str, int] = {} max_len = 0 # tracks our best answer left = 0 # left boundary of the window for right, c in enumerate(s): # If c was seen before AND its last position is # within [left..right), the window contains a duplicate if c in last_seen and last_seen[c] >= left: # Shrink window: move left past the previous occurrence left = last_seen[c] + 1 # Record / update the position of character c last_seen[c] = right # Update the maximum window length seen so far max_len = max(max_len, right - left + 1) return max_len
use std::collections::HashMap; impl Solution { pub fn length_of_longest_substring(s: String) -> i32 { // Map each character to the index where it was last seen let mut last_seen: HashMap<u8, i32> = HashMap::new(); let mut max_len = 0; // tracks our best answer let mut left: i32 = 0; // left boundary of the window let bytes = s.as_bytes(); for right in 0..bytes.len() as i32 { let c = bytes[right as usize]; // If c was seen before AND its last position is // within [left..right), the window contains a duplicate if let Some(&idx) = last_seen.get(&c) { if idx >= left { // Shrink window: move left past the previous occurrence left = idx + 1; } } // Record / update the position of character c last_seen.insert(c, right); // Update the maximum window length seen so far max_len = max_len.max(right - left + 1); } max_len } }
function lengthOfLongestSubstring(s: string): number { // Map each character to the index where it was last seen const map = new Map<string, number>(); let maxLen = 0; // tracks our best answer let left = 0; // left boundary of the window for (let right = 0; right < s.length; right++) { const c = s[right]; // If c was seen before AND its last position is // within [left..right), the window contains a duplicate if (map.has(c) && map.get(c)! >= left) { // Shrink window: move left past the previous occurrence left = map.get(c)! + 1; } // Record / update the position of character c map.set(c, right); // Update the maximum window length seen so far maxLen = Math.max(maxLen, right - left + 1); } return maxLen; }
Why right - left + 1? The window spans indices [left, right] inclusive. That is (right - left + 1) characters. For example, [2, 4] contains indices 2, 3, 4 which is 4 - 2 + 1 = 3 characters.
Enter any string and step through the sliding window algorithm. Watch the window expand and contract in real time.
The right pointer visits each index exactly once, and the left pointer only moves forward — it never backtracks. Every HashMap get, put, and containsKey operation is O(1) amortized, so the total time is O(n) where n is the string length. The HashMap stores at most one entry per distinct character, bounded by both n and the character set size m (e.g., 128 for ASCII), giving O(min(n, m)) space.
Two nested loops generate O(n2) substrings, and each substring is scanned character-by-character to check for duplicates -- up to O(n) per check. A temporary set holding up to n characters accounts for the space.
For each starting index, a Set tracks seen characters and extends the substring in O(1) per step. This eliminates the inner scan but still restarts from each index, giving O(n2) total. The set holds at most min(n, m) entries where m is the charset size.
The right pointer visits each index once, and the left pointer only advances forward -- never backtracks. A HashMap stores the last-seen index for each character, enabling O(1) jumps. Total pointer movement across the entire run is bounded by 2n.
The sliding window amortizes to O(n) because each character enters and leaves the window at most once. The left pointer only moves forward, so across the entire algorithm, it makes at most n total jumps. This is the classic "two-pointer amortization" — even though a single jump can skip many indices, the total work across all jumps is bounded by n.
Review these before coding to avoid predictable interview regressions.
Wrong move: Using `if` instead of `while` leaves the window invalid for multiple iterations.
Usually fails on: Over-limit windows stay invalid and produce wrong lengths/counts.
Fix: Shrink in a `while` loop until the invariant is valid again.