How to Solve: Longest Substring Without Repeating Characters

How to Solve: Longest Substring Without Repeating Characters

(A Complete FAANG-Level Interview Guide)

? Introduction

"This problem appears in 1 out of every 3 onsite interviews—master it, and you’ll prove you can handle sliding windows, edge cases, and optimal trade-offs under pressure."

? WHAT YOU NEED TO KNOW FIRST

Before tackling this problem, ensure you understand: 1. Hash Maps (Dictionaries) – For O(1) lookups and storing character indices. 2. Sliding Window Technique – Maintaining a dynamic window of valid elements. 3. Two-Pointer Technique – Expanding and contracting a window efficiently.

? KEY TECHNIQUES & PATTERNS

? STEP-BY-STEP FRAMEWORK

(Repeatable mental checklist for every sliding window problem.)

1. Define the Window
2. What constitutes a "valid" window? (No repeating characters.)

3. What variables track the window? (left, right pointers.)

4. Initialize Tracking Structures

5. Use a hash map (last_seen) to store the most recent index of each character.

6. Expand the Window (Right Pointer)

7. Move right from 0 to n-1.

8. For each char = s[right], check if it’s already in the window.

9. Adjust the Window (Left Pointer)

10. If char is in last_seen and last_seen[char] >= left, move left to last_seen[char] + 1.

11. Update last_seen[char] = right.

12. Update Maximum Length

13. After each adjustment, compute max_len = max(max_len, right - left + 1).

14. Edge Cases

15. Empty string → return 0.
16. All unique chars → return n.

17. All same chars → return 1.

18. Optimize (Optional)

19. Early exit if n - left <= max_len (no possible longer substring).

? WORKED EXAMPLES

Example 1 – Basic (LeetCode 3)

Problem: Given "abcabcbb", return 3 (substring "abc").

Thought Process

1. Initialize left = 0, max_len = 0, last_seen = {}.
2. Iterate right from 0 to 7:
3. right=0 ('a'): Not in last_seen → max_len=1.
4. right=1 ('b'): Not in last_seen → max_len=2.
5. right=2 ('c'): Not in last_seen → max_len=3.
6. right=3 ('a'): In last_seen at 0 (≥ left) → left=1.
7. Update last_seen['a']=3, max_len=3 ("bca").
8. Continue until right=7.

Python Code

def lengthOfLongestSubstring(s: str) -> int:

    last_seen = {}

    left = max_len = 0

    for right, char in enumerate(s):

        if char in last_seen and last_seen[char] >= left:

            left = last_seen[char] + 1

        last_seen[char] = right

        max_len = max(max_len, right - left + 1)

    return max_len

Time Complexity: O(n) (single pass). Space Complexity: O(min(m, n)) (m = character set size, e.g., 26 for lowercase letters).

Why This Works: - The sliding window ensures we only consider valid substrings. - last_seen tracks the most recent duplicate, allowing left to jump directly to the correct position.

Example 2 – Medium (With Duplicates)

Problem: Given "abba", return 2 (substring "ab" or "ba").

Thought Process

1. right=0 ('a'): max_len=1.
2. right=1 ('b'): max_len=2.
3. right=2 ('b'): Duplicate → left=2 (last_seen['b'] + 1).
4. right=3 ('a'): Duplicate → left=2 (since last_seen['a']=0 < left).
5. Final max_len=2 ("ba").

Python Code

(Same as above—handles duplicates automatically.)

Why This Works: - The condition last_seen[char] >= left ensures we only adjust left if the duplicate is within the current window.

Example 3 – Hard/Follow-Up (At Most K Distinct Characters)

Problem: Given "eceba" and k=2, return 3 (substring "ece").

Thought Process

1. Use a sliding window with a frequency map (char_count).
2. Track distinct_chars (number of unique characters in the window).
3. If distinct_chars > k, move left until distinct_chars <= k.

Python Code

from collections import defaultdict

def lengthOfLongestSubstringKDistinct(s: str, k: int) -> int:

    char_count = defaultdict(int)

    left = max_len = distinct_chars = 0

    for right, char in enumerate(s):

        if char_count[char] == 0:

            distinct_chars += 1

        char_count[char] += 1

        while distinct_chars > k:

            char_count[s[left]] -= 1

            if char_count[s[left]] == 0:

                distinct_chars -= 1

            left += 1

        max_len = max(max_len, right - left + 1)

    return max_len

Time Complexity: O(n) (each character processed at most twice). Space Complexity: O(k) (storing at most k+1 characters).

Why This Works: - The frequency map tracks distinct characters, and the while loop contracts the window when the constraint is violated.

❌ Common Mistakes

? INTERVIEW TrapS

? 1-Minute Recap (Closing Script)

"Here’s your 60-second review before the interview: 1. Sliding window is the key—track left and right pointers. 2. Hash map stores the last seen index of each character. 3. Adjust left only if the duplicate is in the current window (last_seen[char] >= left). 4. Update max_len after every expansion. 5. Edge cases: Empty string, all unique, all same. 6. Optimize: Early exit if the remaining window can’t exceed max_len. You’ve got this—walk in, code it cleanly, and explain your thought process. Good luck!

? Final Notes

• Practice: LeetCode 3, 159, 340.
• Follow-ups: "At most K distinct characters," "Longest substring with at most two distinct characters."
• Whiteboard Tip: Draw the string and mark left/right pointers as you iterate.