3. Longest Substring Without Repeating Characters

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

Input: s = "abcabcbb"
Output: 3
Explanation: The answer is "abc", with the length of 3. Note that "bca" and "cab" are also correct answers.

First Though

My first approach was to treat every character in the string as a possible starting point and scan forward until I encountered a duplicate.

For each starting position, I kept track of the characters already seen in the current substring.

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:

        longest = 0

        for i in range(len(s)):
            seen = [s[i]]
            length = 1

            for j in range(i+1, len(s)):
                if s[j] in seen:
                    break
                else:
                    seen.append(s[j])

                length += 1

            if length > longest:
                longest = length

        return longest

For example, starting at the first character of "abcabcbb":

a
ab
abc
abca
   ^
duplicate

Once the second a is encountered, that substring can no longer be extended without containing a duplicate, so the inner loop stops.

The main problem with this approach is that it repeatedly scans many of the same characters.

There is also an additional cost from using a list for seen. Checking:

s[j] in seen

requires scanning the list, which takes O(k) time in the worst case.

Because the algorithm contains nested loops and performs a linear membership check inside the inner loop, the worst-case runtime is:

• Time: O(n³)
• Space: O(n)

Using a set instead of a list would reduce membership checks to O(1) on average and improve this version to O(n²), but the repeated scanning would still remain.

Improved Approach

Instead of restarting from every possible index, I can maintain a sliding window that always contains unique characters.

The window is defined by two pointers:

• left marks the beginning of the current substring
• right expands the substring one character at a time

A set stores the characters currently inside the window.

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:

        left = 0
        seen = set()
        longest = 0

        for right in range(len(s)):

            while s[right] in seen:
                seen.remove(s[left])
                left += 1

            seen.add(s[right])

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

        return longest

For "abcabcbb", the window initially grows normally:

a
ab
abc

When the next a is encountered:

abca
   ^
duplicate

I move the left side of the window forward until the duplicate is removed:

abc
 ↓
bca

The window can then continue expanding without restarting the search from scratch.

Each character is added to the set at most once and removed at most once, so the total amount of work grows linearly with the size of the string.

• Time: O(n)
• Space: O(min(n, alphabet size))

The sliding-window approach avoids repeatedly examining the same substrings and reduces the runtime from quadratic or worse to linear time.