A complete visual walkthrough of the sliding window technique — from brute force to an elegant O(n) solution.
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; } }
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.
Time: The right pointer visits each index exactly once. The left pointer only moves forward and never revisits an index. All HashMap operations are O(1) amortized. Total: O(n) where n is the string length.
Space: The HashMap stores at most one entry per distinct character. This is bounded by both n (the string length) and m (the size of the character set, e.g. 26 for lowercase English, 128 for ASCII, 65536 for Unicode BMP). So space is O(min(n, m)).
From O(n3) to O(n) — the sliding window technique eliminates redundant work by maintaining the invariant that the window always contains unique characters. Each character is processed at most twice (once when right reaches it, once when left passes it), giving us linear time.