Longest Unique Substring

Return the length of the longest substring of s with no repeating characters.

longestUniqueSubstring(s)

Input format: a single string (may be empty).

Examples

"abcabcbb"   // → 3   ("abc")
"bbbbb"      // → 1   ("b")
"pwwkew"     // → 3   ("wke")
""           // → 0

Walkthrough

Thinking it through

You want the longest stretch with no repeating character. Brute force checks every substring, verifies no duplicates (itself a scan or a fresh set), and tracks the longest that qualifies — roughly O(n²) substrings, each costing up to O(n) to verify.

What triggers a violation

Scanning left to right and extending a window one character at a time, "no repeats" only breaks if the character about to be added already exists inside the current window. So: a variable window, expanding right, shrinking only when the incoming character duplicates something still inside.

Why re-scanning to detect duplicates is wasteful

Scanning backward through the window on every addition to check for a duplicate is O(window size) per step — O(n²) again. The fix: remember, for every character, the most recent index it appeared at. A single hash map lookup, O(1), instead of a re-scan.

The specific shrink condition

Looking up the last index of the character at right:

If it never appeared, or last appeared before the window started (left), it's not a duplicate within the window — include it freely.
If it last appeared at or after left, it's a genuine duplicate inside the window. Since you know exactly where, jump left directly to one position past that occurrence — no need to shrink one step at a time.

Building the approach

Keep a map from character to its most recent index.
For each right, check whether that character's last-seen index is inside the window (>= left). If so, jump left past it.
Update the character's last-seen index to right.
Compute the window's width (right - left + 1) and update the best if larger.
Continue until the string is scanned.

Why this is efficient

Each position is visited once as right advances, and left only moves forward — O(n) instead of O(n²). The map lookup replaces a linear re-scan with a constant-time check, letting the window be maintained incrementally.

main.py

Auto-saved

Console

Press Run to execute your code, or Submit to test and complete this problem.