3. Longest Substring Without Repeating Characters - Explanation

Description

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

A substring is a contiguous sequence of characters within a string.

Example 1:

Input: s = "zxyzxyz"

Output: 3

Explanation: The string "xyz" is the longest without duplicate characters.

Example 2:

Input: s = "xxxx"

Output: 1

Constraints:

0 <= s.length <= 1000
s may consist of printable ASCII characters.

Recommended Time & Space Complexity

You should aim for a solution with O(n) time and O(m) space, where n is the length of the string and m is the number of unique characters in the string.

Hint 1

A brute force solution would be to try the substring starting at index i and try to find the maximum length we can form without duplicates by starting at that index. we can use a hash set to detect duplicates in O(1) time. Can you think of a better way?

Hint 2

We can use the sliding window algorithm. Since we only care about substrings without duplicate characters, the sliding window can help us maintain valid substring with its dynamic nature.

Hint 3

We can iterate through the given string with index r as the right boundary and l as the left boundary of the window. We use a hash set to check if the character is present in the window or not. When we encounter a character at index r that is already present in the window, we shrink the window by incrementing the l pointer until the window no longer contains any duplicates. Also, we remove characters from the hash set that are excluded from the window as the l pointer moves. At each iteration, we update the result with the length of the current window, r - l + 1, if this length is greater than the current result.

Company Tags

Please upgrade to NeetCode Pro to view company tags.

1. Brute Force

Intuition

The brute-force idea is to try starting a substring at every index and keep extending it until we see a repeated character.
For each starting point, we use a set to track the characters we’ve seen so far.
As soon as a duplicate appears, that substring can’t grow anymore, so we stop and record its length.
By doing this for every index, we are guaranteed to find the longest valid substring, though the approach is slow.

Algorithm

Initialize res = 0 to store the maximum length.
For each starting index i:
- Create an empty set charSet.
- Extend the substring by moving j from i forward:
  - If s[j] is already in the set, break.
  - Otherwise, add it to the set.
- Update res with the size of charSet.
Return res after checking all starting positions.

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        res = 0
        for i in range(len(s)):
            charSet = set()
            for j in range(i, len(s)):
                if s[j] in charSet:
                    break
                charSet.add(s[j])
            res = max(res, len(charSet))
        return res

Time & Space Complexity

Time complexity: $O(n * m)$
Space complexity: $O(m)$

Where $n$ is the length of the string and $m$ is the total number of unique characters in the string.

2. Sliding Window

Intuition

Instead of restarting at every index like brute force, we can keep one window that always has unique characters.
We expand the window by moving the right pointer.
If we ever see a repeated character, we shrink the window from the left until the duplicate is removed.
This way, the window always represents a valid substring, and we track its maximum size.
It’s efficient because each character is added and removed at most once.

Algorithm

Create an empty set charSet and two pointers:
- l = left edge of the window
- r = right edge that moves through the string
For each r:
- While s[r] is already in the set:
  - Remove s[l] from the set and move l right.
- Add s[r] to the set.
- Update the result with the window size: r - l + 1.
Return the maximum window size found.

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        charSet = set()
        l = 0
        res = 0

        for r in range(len(s)):
            while s[r] in charSet:
                charSet.remove(s[l])
                l += 1
            charSet.add(s[r])
            res = max(res, r - l + 1)
        return res

Time & Space Complexity

Time complexity: $O(n)$
Space complexity: $O(m)$

Where $n$ is the length of the string and $m$ is the total number of unique characters in the string.

3. Sliding Window (Optimal)

Intuition

Instead of removing characters one by one when we see a repeat, we can jump the left pointer directly to the correct position.
We keep a map that stores the last index where each character appeared.
When a character repeats, the earliest valid starting point moves to one position after its previous occurrence.
This lets us adjust the window in one step and always keep it valid, making the approach fast and clean.

Algorithm

Create a map mp to store the last index of each character.
Initialize:
- l = 0 for the start of the window,
- res = 0 for the longest length.
Loop through the string with index r:
- If s[r] is already in mp, move l to mp[s[r]] + 1, but never backward.
- Update mp[s[r]] = r.
- Update the longest length: res = max(res, r - l + 1).
Return res at the end.

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        mp = {}
        l = 0
        res = 0

        for r in range(len(s)):
            if s[r] in mp:
                l = max(mp[s[r]] + 1, l)
            mp[s[r]] = r
            res = max(res, r - l + 1)
        return res

Time & Space Complexity

Time complexity: $O(n)$
Space complexity: $O(m)$

Where $n$ is the length of the string and $m$ is the total number of unique characters in the string.