Longest Substring Without Repeating Characters

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"

• 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.