Problem Statement

Given a string s, find the length of the longest substring without repeating characters.

A substring is a contiguous non-empty sequence of characters within a string.

Additional information

• 0 <= s.length <= 5 * 10^4
• s consists of English letters, digits, symbols and spaces.

Example 1:

Input: s = "abcabcbb"

Output: 3

Explanation: The answer is "abc", with the length of 3.

Example 2:

Input: s = "bbbbb"

Output: 1

Explanation: The answer is "b", with the length of 1.

Example 3:

Input: s = "pwwkew"

Output: 3

Brute Force

Intuition
We can verify every possible substring to see if it contains unique characters. We start by picking a starting character index i and an ending character index j. For every substring formed from s[i:j], we check if it has any duplicate characters using a set. If it is unique, we compare its length to our maximum found so far.

Algorithm

1. Initialize max_len to 0.
2. Iterate i from 0 to n-1.
3. Iterate j from i to n-1.
4. For the current substring s[i:j+1], check if it contains duplicates.

• Create a set from the substring.
• If len(set) == len(substring), it is unique.

5. If unique, update max_len = max(max_len, j - i + 1).
6. Return max_len.

def length_of_longest_substring(s: str) -> int:
    n = len(s)
    max_len = 0
    
    for i in range(n):
        for j in range(i, n):
            substring = s[i : j + 1]
            if len(set(substring)) == len(substring):
                max_len = max(max_len, len(substring))
                
    return max_len

Time & Space Complexity

• Time complexity: O(n^3)

• Reason: Nested loops give O(n^2) substrings. Checking each substring for uniqueness takes O(n) time.

• Space complexity: O(min(n, m))

• Reason: We need O(k) space for checking a substring of length k, where k is limited by the size of the character set m.

Sliding Window (Optimal)

Intuition
We can use a sliding window approach to scan the string once. We maintain a window defined by two pointers, l (left) and r (right), and a Hash Set to track characters currently inside the window.

We expand the window by moving r to the right. If the character s[r] is already in the set, it means we have a duplicate. We then contract the window from the left by moving l forward and removing characters from the set until the duplicate is gone. Then, we add s[r] and update the max length.

Algorithm

1. Initialize char_set to an empty set.
2. Initialize l (left pointer) to 0.
3. Initialize res (result) to 0.
4. Iterate r (right pointer) from 0 to len(s) - 1:

• While s[r] is in char_set:

• Remove s[l] from char_set.

• Increment l.

• Add s[r] to char_set.

• Update res = max(res, r - l + 1).

5. Return res.

def length_of_longest_substring(s: str) -> int:
    char_set = set()
    l = 0
    res = 0
    
    for r in range(len(s)):
        while s[r] in char_set:
            char_set.remove(s[l])
            l += 1
        char_set.add(s[r])
        res = max(res, r - l + 1)
        
    return res

Time & Space Complexity

• Time complexity: O(n)

• Reason: Each character is added to the set once and removed at most once. The pointers l and r only move forward.

• Space complexity: O(min(n, m))

• Reason: The space required for the set is proportional to the size of the string n or the size of the charset m (e.g., 26 for letters, 128 for ASCII), whichever is smaller.