Sliding Window with HashMap

This problem is a classic application of the sliding window technique. We maintain a window defined by two pointers, left and right, that represents the current substring being examined. A HashMap maps each character to its most recent index, which lets us instantly detect duplicates and jump the left pointer past the previous occurrence.

Implementation steps:

• Use a HashMap<Character, Integer> to store each character's most recent index in the string.
• Expand the window by advancing right one character at a time.
• If the character at right is already in the map and its stored index is within the current window (>= left), move left to map.get(c) + 1 to skip past the duplicate.
• Update the map with the current index and track the maximum window size seen so far.

public int lengthOfLongestSubstring(String s) { Map<Character, Integer> map = new HashMap<>(); // char -> last seen index int maxLen = 0; int left = 0; for (int right = 0; right < s.length(); right++) { char c = s.charAt(right); // If c was seen before and is within the current window, shrink from left if (map.containsKey(c) && map.get(c) >= left) { left = map.get(c) + 1; } map.put(c, right); // update last seen index of c maxLen = Math.max(maxLen, right - left + 1); } return maxLen; }

Trace through Example 1: s = "abcabcbb"

right	char	left	window	maxLen
0	a	0	"a"	1
1	b	0	"ab"	2
2	c	0	"abc"	3
3	a	1	"bca"	3
4	b	2	"cab"	3
5	c	3	"abc"	3
6	b	5	"cb"	3
7	b	7	"b"	3

• Time complexity: O(n) — each character is visited at most twice (once by right, once by left).
• Space complexity: O(min(n, m)) — where m is the size of the character set (e.g. 26 for lowercase letters, 128 for ASCII). The map stores at most one entry per unique character.