Leetcode 3: Longest Substring Without Repeating Characters

Leetcode Link

1. Problem Statement (Simple Explanation)

You are given a string s.
You need to find the length of the longest substring of s that does not contain any repeated characters.

A substring is a contiguous sequence of characters in the string.
You must return an integer length, not the substring itself.

2. Examples

Example 1

Input: s = "abcabcbb"
Output: 3
Explanation:

Some substrings without repeating characters: "abc", "bca", "cab"The longest length is 3.

Example 2

Input: s = "bbbbb"
Output: 1
Explanation:

All substrings that are valid are just "b".

The longest length is 1.

Example 3

Input: s = "pwwkew"
Output: 3
Explanation:

Possible substrings without repetition: "pw", "wke", "kew".

"wke" or "kew" have length 3.

"pwke" is not valid because it’s not contiguous in the original string (p and k are separated by ww).

Constraints

0≤len(s)≤5×104
s consists of English letters, digits, symbols, and spaces.

3. Approach 1 – Brute Force (Check All Substrings)

Intuition

Generate all possible substrings.
For each substring, check if all characters are unique.
Track the maximum length of such substrings.
This is easy to understand but too slow for large strings.

Algorithm (Step-by-Step)

Let n = len(s), maxLen = 0.
For every starting index i from 0 to n - 1:

Use a set to track characters in the current substring.
For every ending index j from i to n - 1:

If s[j] is already in the set, stop (this substring now has a duplicate).
Otherwise, add s[j] to the set.
Update maxLen = max(maxLen, j - i + 1).

Return maxLen.

Pseudo-code (Brute Force)

The function lengthOfLongestSubstring(s) finds the length of the longest substring with all unique characters using a simple double-loop strategy.
It initializes maxLen = 0 and iterates over every possible start index i.
For each i, it creates an empty seen set to track characters in the current substring.
The inner loop extends the substring from j = i onward:

If s[j] is already in seen, a duplicate is encountered, so the inner loop stops—no longer unique substring can continue from i.
Otherwise, it adds s[j] to seen and updates maxLen with the current substring length j - i + 1.

By the end, maxLen holds the maximum length found.

Time and Space Complexity

Time: O(n2)

because we may examine all substrings.

Space (extra): O(k)

where k is the size of the character set (at most O(n), practically bounded).
This will TLE for large inputs and is not the optimal solution.

4. Approach 2 – Sliding Window with Hash Set (O(n))

This is the classic and intuitive optimal approach.

Intuition

We maintain a sliding window [left, right] that always represents a substring with no duplicate characters. We expand the window to the right as long as it stays valid; when we see a duplicate, we shrink from the left until the duplicate is removed.
Think of it as:
right moves forward character by character.
For each character:

If it’s not in the current window → expand the window.
If it is in the current window → shrink from the left until that character is removed.

We track the longest window length that remained valid.

Algorithm (Step-by-Step)

Initialize:

left = 0
maxLen = 0
an empty set seen to store characters currently in the window.

For right from 0 to n - 1:

While s[right] is already in seen:

Remove s[left] from seen.
Increment left (left++).

Add s[right] to seen.
Window [left, right] is now valid (no duplicates).
Update:

maxLen=max(maxLen,right-left+1)
Return maxLen.

Pseudo-code (Sliding Window + Set)

This function computes the length of the longest substring without repeating characters using a sliding window with two pointers.
left and right define the current window [left, right].
A set seen stores the characters currently in the window, ensuring uniqueness.
As right moves from 0 to n-1, we attempt to include s[right].

If s[right] is already in seen, the window is invalid (has a duplicate).
To fix this, we shrink from the left: repeatedly remove s[left] from seen and increment left until the duplicate is gone.
This guarantees the window always contains unique characters.

Once valid, we add s[right] to seen and update maxLen with the window size right - left + 1.

Time and Space Complexity

Time: O(n)

Each character is added to the set at most once and removed at most once.

Space: O(k)

where k is the size of the character set (at most min(n, 256) depending on encoding).

5. Approach 3 – Sliding Window with Index Map (Also O(n))

This is an optimization that often appears in editorial solutions.

Intuition

Instead of shrinking the window one step at a time, we jump the left pointer using a map of last seen positions.
Maintain a map lastIndex[ch] = last index where ch appeared + 1.
When we see a character s[right]:

If it was seen before inside the current window, we move left to max(left, lastIndex[s[right]]).

This keeps the window always valid and doesn’t require a while loop.

Algorithm (Step-by-Step)

Initialize:

left = 0
maxLen = 0
empty map lastIndex

For right from 0 to n - 1:

Let ch = s[right].
If ch is in lastIndex:

Set:

left=max(left,lastIndex[ch])
Update:

lastIndex[ch] = right + 1 (store next valid position)

Update:
maxLen=max(maxLen,right-left+1)
Return maxLen.

Pseudo-code (Sliding Window + Map)

This function finds the length of the longest substring without repeating characters using a sliding window and a hash map (lastIndex) that tracks each character’s most recent position.
left and right bound the current window.
For each character ch = s[right], if ch has been seen, we may need to move left forward to avoid duplicates.
Instead of incrementing step-by-step, we jump:
left = max(left, lastIndex[ch]).
Here, lastIndex[ch] stores the next valid start after the previous occurrence (hence right + 1 when updating).
We then record lastIndex[ch] = right + 1 and update
maxLen = max(maxLen, right - left + 1).
This guarantees the window [left, right] always contains unique characters and never moves left backward.