Longest Substring Without Repeating Characters | Leetcode 3 | Optimal Sliding Window Solution

The problem “Longest Substring Without Repeating Characters” asks for the length of the longest substring in a string s that contains no duplicate characters. A straightforward brute force approach checks all substrings, while the optimal solution uses a sliding window with a hash map to achieve linear time.

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

Here’s the [Problem Link] to begin with.

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
Explanation: The answer is "wke", with the length of 3.
Notice that the answer must be a substring, "pwke" is a subsequence and not a substring.

Constraints:

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

Brute Force (Check All Substrings)

Intuition and Approach

• For every start index i, expand the end index j until a repeat is found.
• Maintain a set/dictionary to track seen characters within the current substring.
• Update the maximum length whenever a longer valid substring is found.
• This is simple but runs in O(n^2) time.

Code

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        if len(s) == 0:
            return 0
        maxans = 0
        for i in range(len(s)):
            set = {}
            for j in range(i, len(s)):
                if s[j] in set:
                    break
                maxans = max(maxans, j - i + 1)
                set[s[j]] = 1
        return maxans

Code Explanation

• Outer loop picks the start index; inner loop grows the substring until a repeat.
• A dictionary acts like a set to check presence in O(1).
• Updates maxans whenever the current window extends without duplicates.

Time and Space Complexity

• Time: O(n^2)
• Space: O(min(n, Σ)) for the set (Σ = character set size)

Conclusion

Great for intuition, but not suitable for large strings due to quadratic time.

Optimal (Sliding Window + Hash Map)

Intuition

Use a sliding window with two pointers (left, right) and a hash map that stores the last seen index of each character:

• As right moves, if s[right] is already in the window, move left to max(left, last_index + 1) to skip past the duplicate.
• Update the answer with the current window size right - left + 1.
• This ensures each character is processed at most twice, yielding O(n) time.

Code

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        hash_map = dict()
        left = 0
        right = 0
        length = 0
        n = len(s)
        while right < n:
            if s[right] in hash_map:
                left = max(hash_map[s[right]] + 1, left)
            hash_map[s[right]] = right
            length = max(length, right - left + 1)
            right += 1
        return length

Code Explanation

• hash_map[ch] = last seen index of ch.
• When encountering a duplicate inside the current window, jump left forward to avoid shrinking one-by-one.
• length tracks the best window size seen so far.

Time and Space Complexity

• Time: O(n) – each index is visited at most twice (once by right, possibly once by left)
• Space: O(min(n, Σ)) for the hash map

Conclusion

The sliding window with a hash map is the optimal solution: clean, efficient, and perfect for production or interviews.

Common Pitfalls and Tips

• Always ensure left only moves forward: left = max(left, last_index + 1).
• The hash map should store the latest index of each character.
• Works seamlessly for all ASCII/Unicode as long as memory allows.

Use Brute Force to understand the mechanics; use the Optimal Sliding Window for performance.

For any changes to the article, kindly email at code@codeanddebug.in or contact us at +91-9712928220.