LeetCode: 3. Longest Substring Without Repeating Characters

3. Longest Substring Without Repeating Characters

Summary

Given a string, find the longest substring without duplicate characters.

Approach

A two-pointer approach (sliding window).

Function

Initialization:

• seen: stores seen characters. The key is the character, and the value is its index.
• p1: the right pointer (starts at 0)
• p2: the left pointer (starts at 0)
• best: the maximum length of a unique substring (starts at 0)

Main loop:

Move p1 from left to right.

• If the current character is not in seen, add it to seen.
• If a duplicate is found and its previous index is greater than or equal to p2, move p2 to seen[ch] + 1.
• Update best if p1 - p2 + 1 is greater than the current best.

Note that p1 and p2 are indices, so the window length is p1 - p2 + 1.

Why these changes?

seen[ch] >= p2 We only care if the previous occurrence is inside the current window. If it is < p2, that duplicate is already outside the window.

p2 = seen[ch] + 1 Example: "abba" When you see the second 'b' at index 2 and the previous 'b' was at index 1, the new window must start from 2, not 1.

p1 - p2 + 1 Window [p2, p1] (inclusive) has length p1 - p2 + 1.

Complexity

Time Complexity: O(N), where N is the length of the string. p1 and p2 each move from left to right. Space Complexity: O(N) for the hash map.

Better implementation.

Let's use enumerate over the s, we can avoid to using the while loop.

And we can improve the naming for p1 and p2. Let's use right and left

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        left = 0
        seen = {}
        best = 0
        for right, ch in enumerate(s):
            if ch in seen and seen[ch] >= left:
                left = seen[ch] + 1
            seen[ch] = right
            best = max(best, right-left+1)
        return best