1. Understand the problem

• Goal: Given a string s, return the length of the longest substring that contains no repeated characters.

• Key points to state out loud in an interview:

1. We’re looking for substring (contiguous). Not subsequence.

2. We return the length only (not the substring itself), unless interviewer asks otherwise.

3. Characters are compared exactly (case sensitive unless specified).

4. Input is a single string s.

General knowledge:

• ASCII is an older, 7-bit character encoding for English text

• While Unicode is a modern, universal standard that supports a vast number of characters from virtually all languages and symbols, including emojis

Potential edge cases:

1. Unicode vs ASCII? (multi-byte characters count as single chars in Python str).

2. Very long string: memory/time constraints matter.

3. Empty string or all-unique or all-duplicate strings are edge cases.

2. Clarifying questions

1. What character set should I assume — ASCII or Unicode? (affects memory assumptions)

2. Maximum length of s? (helps decide strict O(n) needed)

3. Expected time complexity? Is O(n) required?

4. Expected space complexity constraint? (e.g., constant extra space for ASCII)

5. If empty string, should we return 0? (yes — typical)

6. Any special treatment for whitespace or control characters? (usually treat as characters)

7. If they want the substring itself, should we return one substring or all? (usually one)

3. Work through examples

1. s = “” → result 0 (empty string)

2. s = “a” → 1 (single char)

3. s = “aaaa” → 1 (all same)

4. s = “abcabcbb” → 3 (substring “abc”)

5. s = “ “ (single space) → 1 (space is a char)

6. s = “dvdf” → 3 (substring “vdf”; careful: naive mistakes can produce 2)

7. s = “abba” → 2 (substring “ab” or “ba”; check overlapping duplicates)

8. Unicode: s = “😊😊a” → 2 (substring “😊a”)

9. s = “au” → 2

4. Brainstorm 2–3 solutions

4.1. Naive / Brute force

• Generate all substring O(N^2).

• Check unique character per string O(N)

• Time complexity: O(N^3).

• Space complexity: O(1).

4.2. Sliding window with a set (two pointers)

• Maintain window [i, j) with a set of characters. Expand j if new char; if duplicate, move i and remove chars until duplicate removed + Use a HashSet for fast lookup.

Complexity: each char is added/removed at most once.

• Time: O(n).

• Space: O(1).

• Intuiation: Due to from [left,..]. If it start with i, it only can reach until j.

=> We can sure to move the left += 1 to start with another left, and skip traverse from [j + 1, right].

4.3. Optimized sliding window using a map (same idea with intuiation above but smarter)

• Keep a dict mapping char → last index seen.

• Maintain start of window. When we see repeated char c at index j, move start = max(start, last_index[c] + 1).

Idea: Move left until last_index[c], it will skip to traverse while shrinking left.

• Time: O(n) time, Space: O(min(n, charset_size))

5. Implement solutions:

5.1. Brute force

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        res = 0
        for i in range(len(s)):
            charSet = set()
            for j in range(i, len(s)):
                if s[j] in charSet:
                    break
                charSet.add(s[j])
            res = max(res, len(charSet))
        return res

• Optimize it by O(N^2) => By each left, we create a new set and break when not match any more.

• Time: O(N * M)

• Space: O(M) -> M is total unique number characters in set.

5.2. Sliding Window

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        charSet = set()
        l = 0
        res = 0

        for r in range(len(s)):
            while s[r] in charSet:
                charSet.remove(s[l])
                l += 1
            charSet.add(s[r])
            res = max(res, r - l + 1)
        return res

• Note:

  • Remove in hashSet O(1).

  • About case: “abcdeedcba” => O(N^2).

• Time: O(N^2).

• Space: O(M).

5.3. Sliding Window (Optimal)

Idea: Using a hashmap for fast lookup last index.

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        mp = {}
        l = 0
        res = 0

        for r in range(len(s)):
            if s[r] in mp:
                l = max(mp[s[r]] + 1, l)
            mp[s[r]] = r
            res = max(res, r - l + 1)
        return res

• Time: O(N).

• Space: O(M).

6. Run the testcase

🔹 Step-by-step dry run for s = "abcdeedcba"
r	ch	last_index before	start before	Action	start after	last_index after	Window length (r - start + 1)	res
0	a	{}	0	not seen	0	{'a': 0}	1	1
1	b	{'a': 0}	0	not seen	0	{'a': 0, 'b': 1}	2	2
2	c	{'a': 0, 'b': 1}	0	not seen	0	{'a': 0, 'b': 1, 'c': 2}	3	3
3	d	{'a': 0, 'b': 1, 'c': 2}	0	not seen	0	{'a': 0, 'b': 1, 'c': 2, 'd': 3}	4	4
4	e	{'a': 0, 'b': 1, 'c': 2, 'd': 3}	0	not seen	0	{'a': 0, 'b': 1, 'c': 2, 'd': 3, 'e': 4}	5	5
5	e	{'a':0,b:1,c:2,d:3,e:4}	0	duplicate! move start to max(0, 4+1)=5	5	{'a':0,b:1,c:2,d:3,e:5}	1	5
6	d	{'a':0,b:1,c:2,d:3,e:5}	5	seen at 3 (< start), ignore	5	{'a':0,b:1,c:2,d:6,e:5}	2	5
7	c	{'a':0,b:1,c:2,d:6,e:5}	5	seen at 2 (< start), ignore	5	{'a':0,b:1,c:7,d:6,e:5}	3	5
8	b	{'a':0,b:1,c:7,d:6,e:5}	5	seen at 1 (< start), ignore	5	{'a':0,b:8,c:7,d:6,e:5}	4	5
9	a	{'a':0,b:8,c:7,d:6,e:5}	5	seen at 0 (< start), ignore	5	{'a':9,b:8,c:7,d:6,e:5}	5	5