Frequently Asked at Google — This problem has been reported multiple times in recent Google L4 interviews.

Longest Substring Without Repeating Characters (LC 3)

Problem Statement

Given a string s, return the length of the longest substring that contains no repeating characters.

Example 1:

Input:  s = "abcabcbb"
Output: 3
Explanation: "abc" has length 3. "abca" repeats 'a'.

Example 2:

Input:  s = "bbbbb"
Output: 1

Example 3:

Input:  s = "pwwkew"
Output: 3
Explanation: "wke" wins — note "pwke" is a subsequence, not a substring.

Constraints:

• 0 <= s.length <= 5 * 10^4
• s consists of English letters, digits, symbols, and spaces.

Difficulty: Medium

---

Pattern Recognition

• Input structure: a single string.
• What are we searching for? the length of the longest window with a uniqueness property.
• Pattern: sliding window with a hash map (or set).
• Why: The answer is a contiguous subarray, the window grows and shrinks based on a local constraint (duplicates), and each element enters and leaves the window at most once — textbook sliding window.

---

Approach

Brute Force

Check every substring s[i..j] for uniqueness. O(n^3) naive or O(n^2) with incremental set maintenance. TLE at n = 5 * 10^4.

Optimal — Sliding Window

Key Insight: As you extend the window's right edge, if s[right] is already in the window, you can jump the left edge to just past the previous occurrence. This never re-scans characters.

Maintain a map lastIndex[c] = most recent index of character c.

1. left = 0, best = 0.
2. For each right:
   • If s[right] is in lastIndex and lastIndex[s[right]] >= left, jump left = lastIndex[s[right]] + 1.
   • Update lastIndex[s[right]] = right.
   • best = max(best, right - left + 1).

Notice the >= left guard — a stale index from outside the current window should not shrink it.

Time: O(n) — each character is inspected a constant number of times. Space: O(min(n, Σ)) where Σ is the alphabet size.

---

Walkthrough

s = "abcabcbb".

right	s[right]	lastIndex before	Action	left	lastIndex after	best
0	'a'	{}	insert	0		1
1	'b'		insert	0		2
2	'c'		insert	0		3
3	'a'	a:0 ≥ 0	jump left to 1	1		3
4	'b'	b:1 ≥ 1	jump left to 2	2		3
5	'c'	c:2 ≥ 2	jump left to 3	3		3
6	'b'	b:4 ≥ 3	jump left to 5	5		3
7	'b'	b:6 ≥ 5	jump left to 7	7		3

Answer: 3.

---

Implementation

TypeScript

function lengthOfLongestSubstring(s: string): number {
    const lastIndex = new Map<string, number>();
    let left = 0;
    let best = 0;
    for (let right = 0; right < s.length; right++) {
        const ch = s[right];
        const prev = lastIndex.get(ch);
        if (prev !== undefined && prev >= left) {
            left = prev + 1;                    // jump past previous occurrence
        }
        lastIndex.set(ch, right);
        best = Math.max(best, right - left + 1);
    }
    return best;
}

C++

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

Watch out:

1. Forgetting the prev >= left guard causes left to jump backward when a duplicate from an earlier, already-discarded region reappears.
2. Using a plain set and an inner while loop to shrink works (O(n) amortized) but adds clutter. The last-index map collapses the shrink into one jump.
3. Returning left or right instead of best — you want the longest over the entire walk, not just at the end.

---

Complexity Analysis

	Time	Space
Brute Force	O(n^3) or O(n^2)	O(min(n, Σ))
Sliding Window	O(n)	O(min(n, Σ))

Bottleneck: you must read every character, so O(n) is optimal. Space is dominated by the character set actually seen inside the window.

---

Edge Cases

1. Empty string — return 0. Loop never executes.
2. Single character — return 1. Map insertion path runs once.
3. All identical characters — window is always size 1. The prev >= left branch fires every step.
4. No repeats — window never shrinks; answer is s.length.
5. Unicode / non-ASCII — use Map<string, number> in TS or explicit UTF-8 handling in C++.
6. Duplicates far outside current window — the prev >= left guard prevents spurious jumps.

---

Related Problems

• LC 159 — Longest Substring with At Most Two Distinct Characters — Same window, different constraint (distinct-count ≤ 2).
• LC 340 — Longest Substring with At Most K Distinct Characters — Generalization to K distinct.
• LC 76 — Minimum Window Substring — Sliding window with a frequency-match constraint; harder shrink condition.
• LC 424 — Longest Repeating Character Replacement — Window where you tolerate up to k replacements — same skeleton, different invariant.

---

What Is Expected at Each Level

Junior: Recognize sliding window, implement the set-based shrink-loop version correctly, state O(n) time.

Mid-level: Jump-left variant on first try, correctly handle the stale-index case, discuss alphabet-size vs length for space.

Senior (L4 target): Walk through why jump-left is safe, connect to LC 340/76 as cousins, discuss what changes for streaming input (you cannot revisit the left pointer), and comment on Unicode correctness — all of which Google interviewers probe.