Amazon VO Interview: Longest Substring Without Repeating Characters + Follow-up Allow K Repeats (Sliding Window)

In Amazon VO, code cannot be run. This means your verbal explanation and dry run matter as much as the code itself. Here is a full interview-style breakdown of this sliding window problem.

Problem: Longest Substring Without Repeating Characters

Given a string s, find the length of the longest substring with no repeating characters.

Examples:

s = "abcabcbb" → 3 (substring "abc")
s = "bbbbb" → 1 (substring "b")
s = "pwwkew" → 3 (substring "wke")

Explain Your Approach Before Writing Code (Critical for Amazon)

Amazon interviewers cannot run your code. If they don't follow your logic, you fail. Always verbally confirm your approach before writing a single line.

Core Idea: Sliding Window

Maintain two pointers left and right representing the current window [left, right].
Expand the window by moving right one step at a time.
If s[right] already exists in the window, shrink from the left by advancing left until the duplicate is removed.
Update the answer: ans = max(ans, right - left + 1).
Use a hash set to track characters in the window for O(1) lookup.

Why it works: the window always maintains a valid (no-duplicate) state. Both pointers only move rightward, so each character is added and removed at most once — O(n) total.

Code

def lengthOfLongestSubstring(s: str) -> int:
    char_set = set()
    left = 0
    ans = 0

    for right in range(len(s)):
        while s[right] in char_set:
            char_set.remove(s[left])
            left += 1
        char_set.add(s[right])
        ans = max(ans, right - left + 1)

    return ans

Dry Run (Required for Amazon — Code Cannot Be Executed)

s = "abcabcbb"

right	s[right]	Action	left	Window	ans
0	a	add 'a'	0	[a]	1
1	b	add 'b'	0	[a,b]	2
2	c	add 'c'	0	[a,b,c]	3
3	a	remove 'a', left=1; add 'a'	1	[b,c,a]	3
4	b	remove 'b', left=2; add 'b'	2	[c,a,b]	3
5	c	remove 'c', left=3; add 'c'	3	[a,b,c]	3
6	b	shrink until 'b' gone, left=5; add 'b'	5	[c,b]	3
7	b	shrink until 'b' gone, left=7; add 'b'	7	[b]	3

Final answer: 3 ✓

Complexity Analysis

Time: O(n) — each character is added and removed from the set at most once.
Space: O(min(m, n)) — m is the character set size (e.g. 128 for ASCII), n is string length.

Follow-up: Allow At Most K Occurrences Per Character

Variant: instead of "no repeats", allow each character to appear at most k times. Find the longest such substring.

Approach: same sliding window, but replace the set with a HashMap tracking character counts.

Move right, increment count[s[right]].
If count[s[right]] > k, shrink from the left: decrement count[s[left]], remove if zero, advance left.
Update the answer.

Code (k-repeat variant):

from collections import defaultdict

def longestSubstringKRepeats(s: str, k: int) -> int:
    count = defaultdict(int)
    left = 0
    ans = 0

    for right in range(len(s)):
        count[s[right]] += 1
        while count[s[right]] > k:
            count[s[left]] -= 1
            if count[s[left]] == 0:
                del count[s[left]]
            left += 1
        ans = max(ans, right - left + 1)

    return ans

When k = 1 this reduces exactly to the original problem.

Complexity: O(n) time, O(min(m, n)) space — identical to the base problem.

Interview Checklist for Amazon VO

Step	What to Do	Amazon-specific Note
1. Clarify	Restate the problem, ask about edge cases	Never assume
2. Explain approach	Verbally walk through sliding window logic	Talk before coding
3. Write code	Implement cleanly with clear variable names	Readable > clever
4. Dry run	Manually trace through an example	Mandatory — no execution
5. Complexity	State O(n) time, O(min(m,n)) space	Volunteer this, don't wait
6. Follow-up	Extend to k repeats: Set → HashMap	Shows depth of thinking

💬 Need VO Support?

Real-time VO assistance available for Amazon, Google, TikTok, Microsoft, Meta, Uber, and more.

WeChat: Coding0201

📬 Contact

Email: [email protected]
Telegram: @OAVOProxy