Variable Sliding Window — Longest Substring

What does it solve?

Find the length of the longest contiguous substring with no repeating characters. Unlike a fixed window, the size here breathes: the right edge r always pushes forward, and the left edge l catches up only when the window becomes invalid.

Key insight: each character enters the window once (r++) and leaves at most once (l++), so the two pointers together travel 2N steps. That collapses the O(N²) brute force of checking every substring into a single O(N) pass.

The core idea

// expand r, contract l on break
l = 0, best = 0
seen = {}  // char → last index
for r in 0..n-1:
  if s[r] in seen and seen[s[r]] ≥ l:
    l = seen[s[r]] + 1 // jump left
  seen[s[r]] = r
  best = max(best, r - l + 1)

Complexity

Time complexity

O(N)

Right pointer sweeps the string once; left pointer only moves forward. Every index is visited by each pointer at most once — 2N total moves.

Space complexity

O(k)

The seen-map holds at most one entry per distinct character, where k = min(N, charset size). For ASCII that's a constant 128.

Examples & edge cases

Live animation — window expand & contract

inside window [l…r] just added (r) duplicate → shrink best window so far

Input string — window [l … r]

seen map — char → last index

l = — r = — window = — best = —

Step — of —

left (l)

—

window start

right (r)

—

window end

current length

—

r − l + 1

Best length

—

longest so far

Select an example and press Play to start.

✓ Answer: —

Speed Medium

Step-by-step table

Step	Phase	r	char	l	window	length	Action	best

C++ implementation

longest_substring.cpp

#include <bits/stdc++.h>
using namespace std;

// Longest substring without repeating characters
// Variable-size sliding window + last-seen index map
int lengthOfLongestSubstring(string s) {
    unordered_map<char, int> seen; // char -> last index
    int l = 0, best = 0;

    for (int r = 0; r < (int)s.size(); r++) {
        char c = s[r];
        // if c is inside the current window, jump l past its last spot
        if (seen.count(c) && seen[c] >= l) {
            l = seen[c] + 1;
        }
        seen[c] = r;                       // record newest index
        best = max(best, r - l + 1);  // widen answer
    }
    return best;
}

int main() {
    cout << lengthOfLongestSubstring("abcabcbb") << "\n"; // 3 ("abc")
    cout << lengthOfLongestSubstring("pwwkew")   << "\n"; // 3 ("wke")
    return 0;
}

My Notes

📝 Notes ✅

▼

● Start typing to save... 0 chars