Blind 75 Visualized

#2 · Sliding Window

Longest Substring Without Repeating Characters

Given a string, find the length of the longest substring that contains no repeated character.

MediumLeetCode
  • Active
  • Found
  • Window
  • Visited
  • Rejected
step 1 / 1

Pointers

Variables

Hash map / table

Stack / queue

Foundations & data-structure selection

Sliding window (two pointers on one sequence)

A contiguous range [left, right] that expands on the right and contracts on the left. The invariant here: the window never contains a duplicate.

Memory layout

Just two integers. The window is implicit; no substring is ever copied or materialized.

OperationCost
expand rightO(1)
shrink leftO(1), amortized: each index leaves at most once
whole scanO(n)

Hash set / hash map (character → last index)

Answers "is this character in the window?" in O(1), and, as a map, tells us exactly where it was.

Memory layout

Hashed buckets of at most min(n, |alphabet|) entries. For a small fixed alphabet, a flat array indexed by character code replaces hashing entirely: one contiguous block, one load per lookup.

OperationCost
has / get / setO(1) average
spaceO(min(n, σ)), σ = alphabet size

Why it fits

  • Any substring that is duplicate-free stays duplicate-free when you shrink it, so valid windows are monotone. That monotonicity is what allows a window that never moves left past a point it has already left.
  • Each index enters the window once and leaves at most once, so total pointer movement is ≤ 2n even with a nested while loop.
  • Storing the last index (not just presence) lets left jump directly past the duplicate instead of crawling one step at a time.

Why alternatives degrade

Enumerate all substrings:
There are O(n²) substrings, and checking each for duplicates costs O(n) more (O(n³) naively).
Sort the characters:
Destroys contiguity, and the problem is about substrings, which depend on order.
Recursion / DP over (i, j):
Uses O(n²) states for a problem that needs only two moving pointers.

Four approaches, from naive to production

1 · beginner

Restart at every start index

time O(n · min(n, σ))space O(min(n, σ))

For each start, extend right while characters stay unique, using a fresh Set. Track the best length.

int lengthOfLongestSubstring(string s) {
    int best = 0;
    int n = s.size();
    for (int start = 0; start < n; start++) {
        unordered_set<char> seen;
        for (int end = start; end < n; end++) {
            if (seen.count(s[end])) break;
            seen.insert(s[end]);
            best = max(best, end - start + 1);
        }
    }
    return best;
}

Flaws & bottlenecks

  • Throws away all progress at each new start: the window for start+1 overlaps almost entirely with the one just built.
  • Allocates a new Set per start index: n allocations and GC churn.
  • Worst case (all-unique string) is O(n²) time.

Interviewer cross-questions

Where is the redundant work?

Say: When the scan from start dies at a duplicate, everything between start and that duplicate is already known to be unique. Restarting at start+1 re-verifies it. A sliding window keeps that knowledge and only repairs the left edge.

What is the worst-case input?

Say: A string of all-distinct characters (up to the alphabet size), or a long periodic string such as "abcabc…". Every start extends nearly σ characters, so the cost approaches n·σ.

Is the time really O(n²)?

Say: O(n·min(n, σ)): the inner loop can never run longer than the alphabet size, since it stops at the first repeat. For a 26-letter alphabet it is O(26n), which is linear, but the approach does not scale to unbounded alphabets.

2 · intermediate

Sliding window with a Set

time O(n)space O(min(n, σ))

Keep a window [left, right]. On a duplicate, evict from the left one character at a time until the duplicate is gone.

int lengthOfLongestSubstring(string s) {
    unordered_set<char> window;
    int left = 0;
    int best = 0;
    for (int right = 0; right < (int)s.size(); right++) {
        while (window.count(s[right])) {
            window.erase(s[left]);
            left++;
        }
        window.insert(s[right]);
        best = max(best, right - left + 1);
    }
    return best;
}

Flaws & bottlenecks

  • Each character may be touched twice: once added, once evicted (2n operations).
  • Eviction is one step at a time even when we could compute the new left directly.
  • Set stores presence only; we cannot tell where the duplicate was.

Interviewer cross-questions

You have a while inside a for. Why is it O(n) and not O(n²)?

Say: Amortized analysis: left only moves forward and never exceeds right, so across the entire run left makes at most n increments. The while loop body therefore executes at most n times in total, not n times per iteration.

Can left ever move backwards?

Say: No, and that is the key invariant. A window that is valid for right is also valid for any smaller window, so we never need to revisit earlier left values.

Can you remove the inner loop?

Say: Yes. Store each character's last index in a Map, and when a duplicate appears set left = lastIndex + 1 directly. That is the next approach.

3 · advanced

Last-seen map: jump the left pointer

time O(n)space O(min(n, σ))

Map each character to the last index where it appeared. On a repeat inside the window, jump left to one past that index.

int lengthOfLongestSubstring(string s) {
    unordered_map<char, int> lastSeen;
    int left = 0;
    int best = 0;
    for (int right = 0; right < (int)s.size(); right++) {
        char ch = s[right];
        auto it = lastSeen.find(ch);
        if (it != lastSeen.end() && it->second >= left) {
            left = it->second + 1;
        }
        lastSeen[ch] = right;
        best = max(best, right - left + 1);
    }
    return best;
}

Flaws & bottlenecks

  • Map hashing adds a larger constant factor than array indexing.
  • Easy to get wrong: forgetting prev >= left lets a stale index drag left backwards ("abba" is the classic failing test).
  • Strings are indexed by UTF-16 code unit via s[i], which allocates a one-character string each access.

Interviewer cross-questions

Why do you need prev >= left?

Say: The map is never cleaned, so it can hold indices from before the window. In "abba", when the final a arrives its last index is 0, but left is already 2. Setting left = 1 would move the window backwards and wrongly include the repeated b. The check ignores stale entries.

Is the answer correct for Unicode / emoji?

Say: Not by default. s[i] and charCodeAt work on UTF-16 code units, so an emoji is two units. If the spec is about user-perceived characters, iterate with for…of (code points) or Intl.Segmenter (grapheme clusters) and key the map by those.

What if the input is a stream you cannot index?

Say: The algorithm only needs a running index counter and the map, so it works on a stream. To bound memory with a huge alphabet, evict map entries older than left lazily or periodically.

4 · expert

Flat Int32Array + early exit

time O(n)space O(σ) fixed (256 KB)

Replace the Map with an Int32Array indexed by character code (−1 = unseen), read codes with charCodeAt, and stop as soon as the remaining suffix cannot beat the best.

int lengthOfLongestSubstring(const string& s) {
    if (s.empty()) return 0;
    int lastSeen[256]; // byte-indexed: ASCII / Latin-1 input
    fill(begin(lastSeen), end(lastSeen), -1);
    int left = 0;
    int best = 0;
    int n = s.size();
    for (int right = 0; right < n; right++) {
        if (n - left <= best) break;
        unsigned char code = s[right];
        if (lastSeen[code] >= left) left = lastSeen[code] + 1;
        lastSeen[code] = right;
        if (right - left + 1 > best) best = right - left + 1;
    }
    return best;
}

Flaws & bottlenecks

  • Allocates and fills 65 536 Int32 entries (256 KB) even for a 3-character input; for many tiny calls, hoist and reuse or use a smaller table.
  • Indexes by UTF-16 code unit, so surrogate pairs are treated as two characters.
  • Early exit helps only when a long window appears early; worst-case work is unchanged.

Interviewer cross-questions

Why is a typed array faster than a Map here?

Say: It is a single contiguous allocation with a direct index: no hashing, no collision handling, no per-entry objects, and no GC pressure. A lookup is one bounds-checked load, and the JIT can keep it unboxed.

How would you reuse the table across calls without refilling 256 KB?

Say: Store (callId << 16 | index)-style versioned stamps, or keep a monotonically increasing base offset: write base + right, and treat any value < base + left as unseen. A call then needs no clear at all.

Is the early exit a real win?

Say: It is a pure pruning: once s.length − left ≤ best no later window can be longer. It helps on inputs with a long unique run early (like this one), costs one comparison per iteration otherwise, and never changes correctness.

Synchronized code walkthrough

Showing: Restart at every start index — shares the player above; click any step to jump.

int lengthOfLongestSubstring(string s) {
    int best = 0;
    int n = s.size();
    for (int start = 0; start < n; start++) {
        unordered_set<char> seen;
        for (int end = start; end < n; end++) {
            if (seen.count(s[end])) break;
            seen.insert(s[end]);
            best = max(best, end - start + 1);
        }
    }
    return best;
}