Longest Substring Without Repeating Characters

▶

Steps

setup

Initialize variables

Initialize an empty hashmap to store characters and their latest indices, set max_len to 0, and set the left pointer to 0. The right pointer will start iterating from 0.

💡 Setting up these variables is essential to track the current window and the best substring length found so far.

Line:

index_map = {}
max_len = 0
left = 0

💡 We need a way to remember where characters last appeared to detect duplicates efficiently.

expand

Expand window to include 'a' at right=0

Move right pointer to 0, include character 'a'. Since 'a' is not in the hashmap, no need to move left pointer.

💡 Expanding the window by including new characters helps us explore longer substrings without duplicates.

Line:

for right, char in enumerate(s):
    if char in index_map and index_map[char] >= left:

💡 When a new character is unique in the current window, we can safely expand the window.

expand

Expand window to include 'b' at right=1

Move right pointer to 1, include character 'b'. 'b' is not in hashmap, so left pointer stays.

💡 Continuing to expand the window while no duplicates appear increases the substring length.

Line:

if char in index_map and index_map[char] >= left:
    left = index_map[char] + 1

💡 The window can grow as long as no repeated characters are inside.

expand

Expand window to include 'c' at right=2

Move right pointer to 2, include character 'c'. 'c' is new in window, so left pointer stays.

💡 Adding a third unique character extends the substring further.

Line:

index_map[char] = right
max_len = max(max_len, right - left + 1)

💡 The substring 'abc' is currently the longest without repeats.

shrink

Encounter duplicate 'a' at right=3, shrink window

Right pointer moves to 3, character 'a' is already in hashmap at index 0 which is >= left (0). Move left pointer to 1 (0+1) to remove duplicate.

💡 When a duplicate is found inside the window, we must shrink from the left to maintain uniqueness.

Line:

if char in index_map and index_map[char] >= left:
    left = index_map[char] + 1

💡 Shrinking the window removes the earlier occurrence of the duplicate character.

insert

Update hashmap with 'a' at right=3

Update hashmap to record latest index of 'a' as 3.

💡 Updating the character's latest index is crucial for future duplicate detection.

Line:

index_map[char] = right

💡 The hashmap always reflects the most recent position of each character.

shrink

Encounter duplicate 'b' at right=4, shrink window

Right pointer moves to 4, character 'b' is in hashmap at index 1 which is >= left (1), so move left to 2 (1+1) to remove duplicate.

💡 Detecting duplicates requires adjusting the left pointer to maintain a unique substring.

Line:

if char in index_map and index_map[char] >= left:
    left = index_map[char] + 1

💡 The window shrinks to exclude the previous 'b' to keep substring unique.

insert

Update hashmap with 'b' at right=4

Update hashmap to record latest index of 'b' as 4.

💡 Keeping the hashmap updated ensures accurate duplicate detection.

Line:

index_map[char] = right

💡 The hashmap reflects the current window's character positions.

shrink

Encounter duplicate 'c' at right=5, shrink window

Right pointer moves to 5, character 'c' is in hashmap at index 2 which is >= left (2), so move left to 3 (2+1) to remove duplicate.

💡 Adjusting left pointer removes duplicates to maintain substring uniqueness.

Line:

if char in index_map and index_map[char] >= left:
    left = index_map[char] + 1

💡 Window shrinks to exclude the previous 'c'.

insert

Update hashmap with 'c' at right=5

Update hashmap to record latest index of 'c' as 5.

💡 Updating the hashmap keeps track of the most recent character positions.

Line:

index_map[char] = right

💡 The hashmap is always current with the window's characters.

shrink

Encounter duplicate 'b' at right=6, shrink window

Right pointer moves to 6, character 'b' is in hashmap at index 4 which is >= left (3), so move left to 5 (4+1) to remove duplicate.

💡 Shrinking the window removes the earlier duplicate to maintain uniqueness.

Line:

if char in index_map and index_map[char] >= left:
    left = index_map[char] + 1

💡 Window shrinks to exclude the previous 'b'.

insert

Update hashmap with 'b' at right=6

Update hashmap to record latest index of 'b' as 6.

💡 Keeping the hashmap updated is essential for correct duplicate detection.

Line:

index_map[char] = right

💡 The hashmap reflects the current window's character positions.

shrink

Encounter duplicate 'b' at right=7, shrink window

Right pointer moves to 7, character 'b' is in hashmap at index 6 which is >= left (5), so move left to 7 (6+1) to remove duplicate.

💡 When a duplicate is found at the end of the window, the left pointer jumps to exclude it.

Line:

if char in index_map and index_map[char] >= left:
    left = index_map[char] + 1

💡 Window shrinks to exclude the previous 'b'.

insert

Update hashmap with 'b' at right=7

Update hashmap to record latest index of 'b' as 7.

💡 Updating the hashmap ensures the latest character index is stored.

Line:

index_map[char] = right

💡 The hashmap is always current with the window's characters.

reconstruct

End of iteration, return max_len

All characters processed. The maximum length of substring without repeating characters found is 3.

💡 Returning the final answer completes the algorithm.

Line:

return max_len

💡 The longest substring without repeating characters in 'abcabcbb' is length 3.

def lengthOfLongestSubstring(s: str) -> int:
    index_map = {}  # STEP 1
    max_len = 0     # STEP 1
    left = 0        # STEP 1
    for right, char in enumerate(s):  # STEP 2-14
        if char in index_map and index_map[char] >= left:  # STEP 5,7,9,11,13
            left = index_map[char] + 1  # STEP 5,7,9,11,13
        index_map[char] = right  # STEP 6,8,10,12,14
        max_len = max(max_len, right - left + 1)  # STEP 2-14
    return max_len  # STEP 15

if __name__ == '__main__':
    test_str = "abcabcbb"
    print(lengthOfLongestSubstring(test_str))  # Expected output: 3

📊

Longest Substring Without Repeating Characters - Watch the Algorithm Execute, Step by Step

Watching the algorithm step through each character and adjust the window boundaries reveals the core logic behind maintaining a substring without duplicates, which is hard to grasp from code alone.

expand

L ▼

a

0

b

1

c

2

a

3

b

4

c

5

b

6

b

7

Metric: 0

Answer: 0

expand

L=R

a

0

b

1

c

2

a

3

b

4

c

5

b

6

b

7

Window: [a]

Metric: 1

Answer: 1

expand

L ▼

a

0

R ▼

b

1

c

2

a

3

b

4

c

5

b

6

b

7

Window: [a, b]

Metric: 2

Answer: 2

expand

L ▼

a

0

b

1

R ▼

c

2

a

3

b

4

c

5

b

6

b

7

Window: [a, b, c]

Metric: 3

Answer: 3

shrink

a

0

L ▼

b

1

c

2

R ▼

a

3

b

4

c

5

b

6

b

7

Window: [b, c, a]

Metric: 3

Answer: 3

insert

a

0

L ▼

b

1

c

2

R ▼

a

3

b

4

c

5

b

6

b

7

Window: [b, c, a]

Metric: 3

Answer: 3

shrink

a

0

b

1

L ▼

c

2

a

3

R ▼

b

4

c

5

b

6

b

7

Window: [c, a, b]

Metric: 3

Answer: 3

insert

a

0

b

1

L ▼

c

2

a

3

R ▼

b

4

c

5

b

6

b

7

Window: [c, a, b]

Metric: 3

Answer: 3

shrink

a

0

b

1

c

2

L ▼

a

3

b

4

R ▼

c

5

b

6

b

7

Window: [a, b, c]

Metric: 3

Answer: 3

insert

a

0

b

1

c

2

L ▼

a

3

b

4

R ▼

c

5

b

6

b

7

Window: [a, b, c]

Metric: 3

Answer: 3

shrink

a

0

b

1

c

2

a

3

b

4

L ▼

c

5

R ▼

b

6

b

7

Window: [c, b]

Metric: 2

Answer: 3

insert

a

0

b

1

c

2

a

3

b

4

L ▼

c

5

R ▼

b

6

b

7

Window: [c, b]

Metric: 2

Answer: 3

shrink

a

0

b

1

c

2

a

3

b

4

c

5

b

6

L=R

b

7

Window: [b]

Metric: 1

Answer: 3

insert

a

0

b

1

c

2

a

3

b

4

c

5

b

6

L=R

b

7

Window: [b]

Metric: 1

Answer: 3

record_answer

a

0

b

1

c

2

a

3

b

4

c

5

b

6

L=R

b

7

Window: [b]

Metric: 1

Answer: 3

Key Takeaways

✓ The sliding window dynamically expands and shrinks to maintain a substring without duplicates.

This dynamic adjustment is difficult to visualize from code alone but is clear when watching pointer movements step-by-step.

✓ The hashmap stores the latest indices of characters to quickly detect duplicates and decide how to move the left pointer.

Understanding the hashmap's role is crucial because it enables O(n) time complexity by avoiding repeated scans.

✓ When a duplicate character is found, the left pointer jumps forward just past the previous occurrence, not just incremented by one.

This jump avoids unnecessary shrinking and ensures the window always contains unique characters efficiently.

Practice

1. What is the time complexity of the optimal sliding window solution that uses a queue to track zero positions for the Max Consecutive Ones III problem, given an input array of length n and integer k?

medium

A. O(n * k) because each zero can cause multiple window shifts

B. O(n) because each element is visited at most twice by the two pointers

C. O(n^2) because the queue operations inside the loop cause nested behavior

D. O(k) because the queue size is limited to k zeros only

Solution

1. Step 1: Identify loop behavior

   The right pointer iterates over all n elements once, and the left pointer only moves forward when zeros exceed k.

2. Step 2: Analyze queue operations and pointer moves

   Each zero index is enqueued once and dequeued once, so total operations are O(n). However, each zero can cause the left pointer to move multiple times in worst case, leading to O(n * k) complexity.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   While the queue operations are O(n), the window shifts can multiply by k in worst cases [OK]

Hint: Consider worst-case window shifts caused by zeros [OK]

Common Mistakes:

• Assuming strictly linear without considering multiple shifts
• Confusing queue size with total operations
• Ignoring worst-case scenarios

2. What is the time complexity of the optimized sliding window algorithm that uses filtered characters for the minimum window substring problem, where n is the length of s and m is the length of t?

medium

A. O(n) because each character in s is visited at most twice by the two pointers

B. O(n * m) because for each character in s we check all characters in t

C. O(n + m) because we filter s and then slide over filtered characters

D. O(n^2) because shrinking and expanding the window can cause nested loops

Solution

1. Step 1: Identify main loops

   The algorithm uses two pointers moving over filtered characters, each pointer advances at most n times.

2. Step 2: Analyze filtering and counting

   Filtering s takes O(n), sliding window over filtered characters is O(n) since each character is visited twice max.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Two-pointer sliding window is linear time [OK]

Hint: Two pointers each move forward at most n times [OK]

Common Mistakes:

• Confusing filtering cost
• Assuming nested loops cause O(n^2)
• Ignoring that each pointer moves only forward

3. The following code attempts to implement the optimized sliding window for minimum window substring. Identify the line that contains a subtle bug causing incorrect results on some inputs.

medium

A. Line checking if window_count[c] == t_count[c] to increment have

B. Line checking if window_count[filtered_s[left][1]] <= t_count[filtered_s[left][1]] to decrement have

C. Line decrementing window_count for filtered_s[left][1]

D. Line updating res and res_len when a smaller window is found

Solution

1. Step 1: Understand decrement condition

   The condition to decrement have must trigger only when count falls below required, i.e., <, not <=.

2. Step 2: Identify bug effect

   Using <= causes have to decrement prematurely, leading to missing valid windows and incorrect results.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Correct condition is window_count[...] < t_count[...] [OK]

Hint: Decrement have only when count drops below required [OK]

Common Mistakes:

• Using <= instead of < for decrement
• Not updating have when shrinking
• Incorrect res update logic

4. Suppose the input array can contain negative numbers as well as 0s and 1s. Which of the following statements about using the two-pointer sliding window approach to count subarrays with sum equal to goal is correct?

hard

A. Using prefix sums with a hash map is no longer valid when negative numbers are present.

B. The two-pointer sliding window approach still works correctly with minor modifications to handle negative numbers.

C. The two-pointer sliding window approach fails because the window sum can decrease unpredictably, causing infinite loops or incorrect counts.

D. Brute force is the only correct approach when negative numbers are allowed.

Solution

1. Step 1: Understand sliding window assumptions

   Sliding window relies on the sum increasing when expanding right pointer and decreasing when moving left pointer, which holds for non-negative numbers.

2. Step 2: Effect of negative numbers

   Negative numbers can cause sum to decrease when expanding right pointer, breaking monotonicity and causing infinite loops or incorrect counts.

3. Step 3: Alternative approaches

   Prefix sums with hash map still work with negatives; brute force is correct but inefficient.

4. Final Answer:

   Option C -> Option C

5. Quick Check:

   Sliding window fails with negative numbers due to non-monotonic sum [OK]

Hint: Sliding window requires non-negative elements for monotonic sum [OK]

Common Mistakes:

• Assuming sliding window works unchanged with negatives
• Thinking prefix sums with hash map fail with negatives
• Believing brute force is the only solution

5. Suppose the problem is modified so that elements in the array can be reused any number of times to form contiguous subarrays (i.e., subarrays can wrap around or repeat elements). Which of the following statements about adapting the sliding window algorithm is correct?

hard

A. The original sliding window algorithm works without changes because product updates remain valid with repeated elements.

B. Using a max-heap to track products allows efficient counting of repeated-element subarrays.

C. The sliding window approach fails because the window can grow indefinitely due to element reuse, requiring a different approach like dynamic programming.

D. We can fix the sliding window by resetting the window whenever product exceeds k, but counting subarrays remains the same.

Solution

1. Step 1: Understand element reuse impact

   Allowing reuse means subarrays can be infinitely long by repeating elements, so the window can grow without bound.

2. Step 2: Sliding window limitation

   Sliding window relies on finite array length and shrinking window when product exceeds k; infinite repetition breaks this logic.

3. Step 3: Alternative approach needed

   Dynamic programming or other methods are needed to handle infinite or repeated elements properly.

4. Final Answer:

   Option C -> Option C

5. Quick Check:

   Infinite growth breaks sliding window assumptions -> need different approach [OK]

Hint: Infinite repetition breaks sliding window shrinking logic [OK]

Common Mistakes:

• Assuming sliding window works unchanged
• Trying to fix by resets only