Stop Using HashSet: Optimize LeetCode #3 Sliding Window from 8 ms to 2 ms

1. What the Sliding Window Actually Slides

The sliding‑window technique is a specialized form of the two‑pointer method. Its core idea is "one in, one out": the right pointer expands the window by adding new characters, while the left pointer contracts the window when the current state becomes invalid.

Right pointer (right) : continuously expands, swallowing new elements to seek a feasible solution.

Left pointer (left) : when the window becomes illegal, it shrinks, discarding old elements until the window is legal again.

A common mistake is updating the result at the wrong moment; the position of the update differs between longest‑substring and shortest‑substring problems.

Universal Java Template

Two templates are provided depending on whether the goal is to find the longest/maximum or the shortest/minimum:

for (int right = 0; right < n; right++) {
    // 1. Add s[right] to the window, update state

    // 2. While window is illegal, shrink left boundary
    while (window state not satisfied) {
        // Remove s[left] from window, update state
        left++;
    }

    // 3. Window is now legal, update result
    maxLen = Math.max(maxLen, right - left + 1);
}

The key distinction is where the while loop appears: for longest‑substring the update happens after the loop, for shortest‑substring it happens inside the loop.

2. Code "Public Execution": The HashSet Pitfall

A reader submitted a HashSet‑based solution that passes but runs in 8 ms, beating only about 30 % of users. The code uses HashSet<Character>, which triggers automatic boxing of char to Character. Each add, remove, and contains incurs hash computation, possible bucket traversal, and object allocation, inflating the constant factor dramatically.

Why HashSet Is Slow

Boxing creates temporary objects; the hash table must compute hashes, locate buckets, and resolve collisions (sometimes converting a bucket list to a red‑black tree). This overhead makes the O(N) algorithm feel "half‑broken" in practice.

3. Performance Squeezing in Practice: From 8 ms to 2 ms

Level 1: Replace HashSet with a Boolean Array

For ASCII characters (128 possible values), a simple boolean[] can record presence without any boxing. The window update becomes a direct memory address calculation ( base + index * elementSize), yielding high CPU‑cache locality.

public int lengthOfLongestSubstring(String s) {
    int left = 0, ans = 0;
    boolean[] window = new boolean[128];
    for (int right = 0; right < s.length(); right++) {
        char c = s.charAt(right);
        while (window[c]) {
            window[s.charAt(left)] = false;
            left++;
        }
        window[c] = true;
        ans = Math.max(ans, right - left + 1);
    }
    return ans;
}

Result: runtime stabilises around 2 ms, beating over 90 % of submissions.

Level 2: Index Jumping with an Int Array

Instead of shrinking step‑by‑step, store the next index after the last occurrence of each character in an int[]. When a duplicate is found, jump the left pointer directly to that stored index, eliminating the inner while loop.

public int lengthOfLongestSubstring(String s) {
    int left = 0, ans = 0;
    int[] lastIndex = new int[128];
    for (int right = 0; right < s.length(); right++) {
        char c = s.charAt(right);
        if (lastIndex[c] > left) {
            left = lastIndex[c];
        }
        lastIndex[c] = right + 1;
        ans = Math.max(ans, right - left + 1);
    }
    return ans;
}

Effect: inner loop disappears, time remains ~2 ms. The constant factor is the same as Level 1 for the given test size, but the technique illustrates a more powerful "space‑for‑time" mindset useful in KMP, Manacher, and jump‑game problems.

Why Level 2 Isn’t Faster on LeetCode

LeetCode’s timing has inherent variance (1 ms–3 ms) and the test cases are limited to a few‑tens of thousands of characters, so the constant‑time advantage of index jumping is not observable. The real value lies in the upgraded thinking: moving from incremental shrinking to direct jumps.

4. Pitfall Summary

Use arrays for character counting / duplicate detection. For lowercase letters, int[26]; for full ASCII, int[128]. Avoid HashMap<Character, Integer> or HashSet<Character> because arrays have contiguous memory and superior cache behaviour.

Update result timing. For longest‑substring, update after the shrinking while loop (outside); for shortest‑substring, update inside the loop (while it’s still legal).

Avoid the "negative‑number trap". Sliding windows require monotonic state changes; if the window’s metric can decrease (e.g., sums with negative numbers), the technique fails and you must switch to prefix‑sum + monotonic queue or hash‑table approaches.

Conclusion

Algorithmic problems are not just about getting an AC answer; they are a laboratory for understanding data‑structure characteristics and time‑space trade‑offs. By replacing a boxed HashSet with a plain boolean[], then advancing to an int[] that records the last index, the runtime drops from 8 ms to roughly 2 ms. More importantly, the mindset shift—from "shrink step by step" to "jump directly"—is a reusable pattern for many advanced problems.