Skip to content
LeetCode 3: 5 Sliding Window Pitfalls That Fail 90% of Candidates

LeetCode 3: 5 Sliding Window Pitfalls That Fail 90% of Candidates

This article dissects LeetCode 3's sliding window solution from an interviewer's perspective, covering three code versions (HashSet, HashMap, int[128] array), five common pitfalls including the 'abba' trap, seven follow-up questions, complexity analysis, and a template to solve five related problems.

Rain's Path to Java Mastery
Rain's Path to Java Mastery
Rain's Path to Java Mastery

Interviewer's Perspective on LeetCode 3

LeetCode 3 "Longest Substring Without Repeating Characters" appears frequently in algorithm rounds at ByteDance, Meituan, and DiDi. Many candidates memorize the solution but fail when asked about optimizations or edge cases. This article breaks down the problem from an interviewer's viewpoint: what is tested, how to evolve from brute force to optimal, three production-ready implementations, five fatal pitfalls, seven common follow-up questions, and a reusable sliding window template.

What Interviewers Actually Test

Interviewers evaluate three dimensions:

Algorithmic thinking : Can you progress from O(n³) brute force to O(n) sliding window? (Weight: ⭐⭐⭐⭐⭐)

Coding ability : Is your two-pointer + hash boundary handling clean? (Weight: ⭐⭐⭐⭐)

Depth follow-ups : Can you answer "What if HashMap is not allowed?" (Weight: ⭐⭐⭐)

Showing a complete thought process matters more than dumping the optimal solution immediately.

Clarifying Questions Before Coding

Character set? ASCII vs Unicode → decides int[128] vs HashMap<Character,Integer>.

Return length or substring? This problem returns length.

Empty string? Returns 0.

Key phrases: continuous (not subsequence) and no repeats . Seeing "substring + continuous interval + max/min length" should trigger "sliding window".

Thought Evolution: From Brute Force to Optimal

Brute Force: O(n³) ❌

Three nested loops: enumerate all substrings, check duplicates with HashSet. Too slow; mention only as a stepping stone.

Sliding Window Core Insight

If s[i..j] has a duplicate, then s[i..j+1] , s[i..j+2] … all have duplicates. Therefore the left pointer only moves right, never backtracks.

Visualize the window as a greedy snake: right is the head swallowing characters; when a duplicate is swallowed, the tail ( left) contracts to expel the earlier occurrence. The invariant: window always contains unique characters.

Optimization key: left pointer doesn't move one step at a time; a hash map/array records each character's last index, allowing O(1) jump.

Visualization Walkthrough for s = "abcabcbb"

The following table traces each step:

right=0, char='a' : left=0, window=[a], maxLen=1, record a→0

right=1, char='b' : left=0, window=[a,b], maxLen=2, record b→1

right=2, char='c' : left=0, window=[a,b,c], maxLen=3, record c→2

right=3, char='a' : a last at 0 ≥ left → left=1, window=[b,c,a], maxLen=3, record a→3

right=4, char='b' : b last at 1 ≥ left → left=2, window=[c,a,b], maxLen=3, record b→4

right=5, char='c' : c last at 2 ≥ left → left=3, window=[a,b,c], maxLen=3, record c→5

right=6, char='b' : b last at 4 ≥ left → left=5, window=[c,b], maxLen=3, record b→6

right=7, char='b' : b last at 6 ≥ left → left=7, window=[b], maxLen=3, record b→7

Mnemonic: Right pointer expands, left pointer jumps, both only move right, never retreat. This monotonicity guarantees O(n).

Four Solutions Compared

Brute force + HashSet : O(n³) time, O(min(m,n)) space → reject.

HashSet sliding window (left shrinks one by one) : O(n) amortized (2n ops), O(min(m,n)) space → acceptable, easy to understand.

HashMap sliding window (left jumps) : O(n) time, O(min(m,n)) space → standard answer.

int[128] array sliding window : O(n) time, O(1) space (fixed charset) → optimal, interview bonus.

m = charset size (ASCII=128), n = string length. Array space is strictly O(1) because charset size is constant.

HashSet version shrinks left via inner while loop calling remove repeatedly; HashMap/array versions jump left via lastIndex[c] + 1, eliminating the inner loop's constant overhead. Mentioning this distinction impresses interviewers.

Three Must-Memorize Code Versions

Version 1: HashSet Classic (Correctness First)

class Solution {
    public int lengthOfLongestSubstring(String s) {
        Set<Character> set = new HashSet<>();
        int left = 0, maxLen = 0;
        for (int right = 0; right < s.length(); right++) {
            char c = s.charAt(right);
            // 🔥 Shrink left continuously while duplicate exists
            while (set.contains(c)) {
                set.remove(s.charAt(left++));
            }
            set.add(c);
            maxLen = Math.max(maxLen, right - left + 1);
        }
        return maxLen;
    }
}

Version 2: HashMap Records Latest Index (General & Safe)

public int lengthOfLongestSubstring(String s) {
    Map<Character, Integer> last = new HashMap<>(); // char -> latest index
    int left = 0, ans = 0;
    for (int right = 0; right < s.length(); right++) {
        char c = s.charAt(right);
        if (last.containsKey(c)) {
            // ⭐ Critical: Math.max ensures left only advances
            left = Math.max(left, last.get(c) + 1);
        }
        last.put(c, right);
        ans = Math.max(ans, right - left + 1);
    }
    return ans;
}

Version 3: int[128] Array (Performance Crusher)

When charset is ASCII, replace HashMap with int[128]: no boxing, no hash collisions, cache-friendly, 3-5x constant-factor speedup.

class Solution {
    public int lengthOfLongestSubstring(String s) {
        // ASCII has 128 chars; last[c] stores last occurrence index
        int[] last = new int[128];
        // ⚠️ Must initialize to -1, otherwise index 0 is misjudged as "seen"
        Arrays.fill(last, -1);

        int left = 0, maxLen = 0;
        for (int right = 0; right < s.length(); right++) {
            char c = s.charAt(right);
            // 🔥 One line merges "check duplicate + shrink": -1+1=0 naturally handles first occurrence
            left = Math.max(left, last[c] + 1);
            last[c] = right;
            maxLen = Math.max(maxLen, right - left + 1);
        }
        return maxLen;
    }
}
Highlight: last[c] = -1 initialization makes last[c] + 1 = 0 , so first-seen characters need no if branch — one less line, one less bug. HashMap&lt;Character,Integer&gt; boxes each char to Character on every get/put , creating many temporary objects; int[] uses direct base+offset access, an order of magnitude faster.

Two equivalent "fancy" array variants for follow-up flexibility:

// Variant A: store "next valid start position", initial 0 matches string start, no null check
int[] nextValidPos = new int[128];
for (int right = 0; right < s.length(); right++) {
    char c = s.charAt(right);
    left = Math.max(left, nextValidPos[c]);
    nextValidPos[c] = right + 1;
    maxLen = Math.max(maxLen, right - left + 1);
}

// Variant B: 1-based index, store right+1, 0 means "not seen"
int[] last = new int[128];
for (int right = 0; right < s.length(); right++) {
    char c = s.charAt(right);
    if (last[c] > left) {        // last[c] stores pos+1, > left means inside window
        left = last[c];          // directly the next position
    }
    last[c] = right + 1;
    maxLen = Math.max(maxLen, right - left + 1);
}

Five Fatal Pitfalls (Each Has Eliminated Candidates)

Left pointer backtrack — Classic counterexample "abba". Without Math.max or last[c] >= left guard, left moves backward, window becomes invalid. Solution: left = Math.max(left, last[c]+1).

while written as if (HashSet version) — In "pwwkew", single removal leaves duplicate inside window. Must use while to shrink until clean.

int[] initialization missing fill(-1) — Default zeros cause index 0 to be misread as "already seen". Fix: Arrays.fill(last, -1) or use 1-based variant.

Window length missing +1 — Closed interval [left, right] length is right - left + 1.

Charset adaptation — Blindly using HashMap wastes performance; int[128] overflows for Chinese. ASCII → array; Chinese (BMP) → int[65536] or HashMap; emoji → codePointAt + Map<Integer,Integer>.

Deep Dive: The abba Trap

Counterexample: s = "abba"

right=2 sees second 'b': last['b']=1 ≥ left=0 → left=2
right=3 sees second 'a': last['a']=0 but 0 < left=2, not in window!

❌ Without guard: left pulled back to 1, window becomes "bba", answer 3 (wrong)
✅ With Math.max: left = max(2, 0+1) = 2, stays, answer = 2 (correct)
Interview talking point: "Left pointer monotonic non-retreat is the core guarantee of O(n) amortized complexity, so we must check &gt;= left or use Math.max as a fence."

Bonus insight: "Store new, don't delete old." Expired indices outside window ( < left) are naturally ignored by the guard, more elegant than HashSet's repeated removals.

Complexity Analysis: Why O(n) Not O(n²)

Standard answer: Both pointers only move forward, never backward. Each character enters and leaves the window at most once → total operations ≤ 2n → amortized O(1) per step.

Edge cases need no special handling; loop structure naturally covers:

Empty string "" → loop skipped, returns 0 ✅

All duplicates "bbbbb" → left sticks to right, returns 1 ✅

Single char → 1 ✅; all unique → n ✅

Seven Interviewer Follow-Up Questions

Can time be optimized to O(log n)? No. Must scan every character at least once → O(n) is theoretical lower bound. Similarly, extra space cannot be eliminated without degrading to O(n²); "remember last position" requires O(m) space.

Without HashMap? (Asked at DiDi) Use int[128] array version. ASCII array access is multiples faster than HashMap, no boxing, no GC pressure.

Chinese/Unicode characters? Java char covers BMP. int[128] insufficient → switch to HashMap<Character,Integer> or int[65536] (space for safety). For emoji/supplementary planes (surrogate pairs), char splits them — must iterate with codePointAt(i), use Map<Integer,Integer>, advance by Character.charCount(cp).

Return the substring itself, not just length? Track maxStart alongside maxLen when updating max; finally return s.substring(maxStart, maxStart + maxLen).

At most k duplicate characters allowed? Change duplicate detection to "window char count > k triggers shrink", use int[128] as counter; skeleton unchanged.

Huge/streaming input? Algorithm is single-pass, stores only O(m) state → naturally fits streaming; replace s.charAt with incremental character reads.

Real-world business use? Redis sliding window rate limiting ! Redis uses ZSet to store request timestamps, sliding window counts requests — same essence: "maintain a valid interval." Also TCP flow control, video streaming sliding window retransmission, log stream real-time deduplication.

One Template Solves Five Problems

LeetCode 3 is the mother problem for sliding window. Master this skeleton:

int left = 0, ans = 0;
for (int right = 0; right < n; right++) {
    // 1. Add s[right] to window (update count/index)
    // 2. while (window invalid) shrink left, remove s[left]
    // 3. ans = Math.max(ans, right - left + 1);
}

Variations only change one or two lines:

LC 340 Longest Substring with At Most K Distinct Characters → step 2: while (map.size() > k) LC 424 Longest Repeating Character Replacement → step 2: while (len - maxFreq > k) LC 438 Find All Anagrams → fixed window size, step 3 becomes collect results

LC 76 Minimum Window Substring → step 2 validity condition + step 3 take min

LC 209 Minimum Size Subarray Sum → window tracks "sum" instead of characters

Bonus talking point: "Sliding window's essence is monotonicity — right pointer expands monotonically, left pointer contracts monotonically, neither backtracks, reducing O(n²) to O(n). This property applies to LC 76, 209, etc."

Interview Rhythm & 30-Second Recitation

Soft skills differentiate equal answers:

Don't dump optimal solution first : Explain brute force flaw, then sliding window motivation, then incremental optimizations. Complete reasoning > memorized code.

Proactively mention pitfalls : Bring up abba, bbbbb, array vs HashMap trade-offs yourself.

Analyze complexity aloud : State time/space and derivation — standard bonus.

Dry-run examples after coding : Verbally trace abcabcbb, pwwkew, abba to self-verify.

30-second script (internalize, then use your own words): "I use a sliding window with left / right pointers. right expands rightward while a Map records each character's latest index. When right encounters a character whose last occurrence lies inside the current window ( last[c] &gt;= left ), a conflict occurs, so I jump left directly to last[c] + 1 . Throughout, I maintain the maximum of right - left + 1 . Because both pointers only move right, each character is visited at most twice → O(n) time, space equals charset size. Two details: first, the &gt;= left guard is mandatory, otherwise abba causes left to retreat; second, when charset is known (e.g., ASCII), I replace HashMap with int[128] to avoid autoboxing overhead."

Final Summary

One-sentence essence: Sliding window uses the "window has no duplicates" invariant to collapse three nested loops into a single pass; the critical detail is preventing left-pointer backtrack.

Mnemonic: Right pointer charges, left pointer teleports, max prevents retreat, array boosts speed.

Original Source

Signed-in readers can open the original source through BestHub's protected redirect.

Sign in to view source
Republication Notice

This article has been distilled and summarized from source material, then republished for learning and reference. If you believe it infringes your rights, please contactadmin@besthub.devand we will review it promptly.

interview preparationsliding windowalgorithm interviewTime Complexitylongest substringabba trapHashMap vs arrayLeetCode 3
Reader feedback

How this landed with the community

Sign in to like

Rate this article

Was this worth your time?

Sign in to rate
Discussion

0 Comments

Thoughtful readers leave field notes, pushback, and hard-won operational detail here.