3. Longest Substring Without Repeating Characters

Medium

Problem:

Return the length of the longest substring without repeating characters.

Input: s = "abcabcbb"
Output: 3
Explanation: The answer is "abc", with the length of 3.

Input: s = "bbbbb"
Output: 1
Explanation: The answer is "b", with the length of 1.

Input: s = "pwwkew"
Output: 3
Explanation: The answer is "wke", with the length of 3.
Notice that the answer must be a substring, "pwke" is a subsequence and not a substring.

https://leetcode.com/problems/longest-substring-without-repeating-characters/

Solution:

Sliding Window and Two Pointers

Using a sliding window, move one step to the right at a time, adjusting the window size with two pointers to ensure that all characters within the window are unique.

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        used = {}
        max_length = start = 0

        for index, char in enumerate(s):
            if char in used and start <= used[char]:
                start = used[char] + 1
            else:
                max_length = max(max_length, index - start + 1)
            
            used[char] = index
        
        return max_length

Example: abcabcbb

For the string abcabcbb:

• The longest substring without repeating characters is abc, which has a length of 3.

• The function would return 3.

Detailed walkthrough:

1. a (start=0, max_length=1)

2. ab (start=0, max_length=2)

3. abc (start=0, max_length=3)

4. bca (start=1, max_length=3) - here, since we found another a, start moves to just after the previous a.

5. cab (start=2, max_length=3)

6. abc (start=3, max_length=3) - even though we found another a, this a's previous occurrence is outside the current window. Therefore, max_length doesn't change.

7. cb (start=4, max_length=3) - same logic, start moves to after the previous b.

8. b (start=7, max_length=3)

In the end, the function returns max_length, which is 3.

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        # two pointer
        
        i, j = 0, 0
        res = 0
        chars = set()

        while j < len(s):
            if s[j] not in chars:
                chars.add(s[j])
                j += 1
                res = max(res, j - i)
            else:
                chars.remove(s[i])
                i += 1
        
        return res