Longest Substring Without Repeating Characters

Given a string s, return the length of the longest substring with no repeating characters.

A substring is a continuous part of the string.

Only the length is required.

Brute Force Approach

A direct solution examines every possible substring. Every pair of start and end indices defines one contiguous substring, so complete enumeration guarantees coverage of every possible answer.

A separate helper checks character uniqueness inside each selected range. A fresh set stores characters from only the current substring. Complete rechecking keeps the logic simple, but repeated scanning of overlapping substrings creates considerable extra work.

Algorithm

• Initialize maxLen with 0 because no valid substring has been found initially.

• Traverse every possible start index from 0 to N - 1.

• For each start, move end from start toward N - 1 so every substring beginning at that position can be examined.

• Pass s[start...end] to a helper that uses a fresh set to determine whether all characters in the range are distinct.

• If the helper finds a duplicate, break the current end traversal, because extending the same substring cannot remove that duplicate.

• Otherwise, update maxLen with end - start + 1, then return maxLen after all starting positions are processed.

Dry Run

Solution

Complexity Analysis

Time Complexity: O(N³), where N represents the string length. O(N²) substrings exist, and every uniqueness check may scan up to N characters.

Space Complexity: O(N), because the helper set may store every character from one substring in the worst case.

Better Approach

The Brute Force Approach checks every completed substring from the beginning. A more natural improvement grows a substring one character at a time from each starting position.

A set tracks characters already present in the current growing substring. After a repeated character appears, every longer substring from the same start remains invalid because the repeated pair stays inside the range. The current start can therefore stop immediately.

Algorithm

• Initialize maxLen with 0 to store the longest duplicate-free length found so far.

• Traverse every start index because the longest valid substring may begin at any position.

• Create a fresh seen set for every start index so characters from a previous starting position cannot affect the new substring.

• Move end from start toward the final index and check s[end] before insertion.

• Stop the current expansion when s[end] already exists in seen, because every longer substring from the same start will retain the duplicate; otherwise, insert the character and update maxLen.

• Return maxLen after expansion from every starting position has finished.

Dry Run

Solution

Complexity Analysis

Time Complexity: O(N²), where N represents the string length. Expansion from each starting position may scan many later characters.

Space Complexity: O(N), because the set may store every distinct character from one growing substring.

Optimal Approach 1

Instead of restarting from every index, maintain one valid sliding window.

A map stores the latest index of each character. If s[right] previously appeared inside the current window, left can jump directly after that occurrence. If the saved index lies before left, it belongs to an old window and can be ignored.

This keeps both pointers moving only forward.

Algorithm

• Create lastSeen for storing the latest index of every character, and initialize left and maxLen with 0.

• Move right from 0 to N - 1 so every character becomes the right boundary exactly once.

• Read the previous index of s[right]; only an index greater than or equal to left represents a duplicate inside the active window.

• Move left to lastSeen[s[right]] + 1 after an active duplicate appears, because the jump removes the older occurrence without unnecessary one-by-one movement.

• Store right as the latest index of the current character, then update maxLen with right - left + 1 because the window is valid after the possible jump.

• Return maxLen after right reaches the end of the string.

Dry Run

Solution

Complexity Analysis

Time Complexity: O(N), where N represents the string length. Pointer right processes every character once, while pointer left only moves forward.

Space Complexity: O(N), because lastSeen may store an entry for every distinct character in the string.

Optimal Approach 2

When the character set is limited to 26 lowercase English letters, a hash map is unnecessary.

Use an array of size 26, where each position tells whether a character is currently present in the sliding window. When a duplicate enters, move left forward and mark outgoing characters as absent until the duplicate is removed.

Since the array size is fixed, the auxiliary space remains constant.

Algorithm

• Create a boolean or integer array present of size 26, where present[c - 'a'] tells whether character c currently exists inside the window.

• Initialize left = 0 and maxLen = 0 to represent the beginning of the active window and the best length found.

• Move right from 0 to N - 1 and convert the current character into its array index using s[right] - 'a'.

• While the current character is already marked as present, remove s[left] from the active window by setting its corresponding position to 0, then move left forward.

• Mark s[right] as present by setting its position to 1. The window is now duplicate-free, so update maxLen with right - left + 1.

• Return maxLen after the complete string is processed.

Dry Run

Solution

Complexity Analysis

Time Complexity: O(N), because each character enters the window once and leaves it at most once.

Space Complexity: O(1), because the presence array always contains exactly 26 positions.