Longest Substring Without Repeating Characters Leetcode

Introduction

The longest substring without repeating characters leetcode problem challenges programmers to find the maximum length of a substring where each character appears only once. This classic coding interview question tests your ability to manipulate strings efficiently and manage state with minimal overhead Took long enough..

Understanding the Problem

Problem Statement

Given a string s, return the length of the longest substring that contains no duplicate characters. Take this: in the string "abcabcbb" the longest substring without repeating characters is "abc", which has a length of 3.

Key Insights

• The solution must examine each character once; nested loops that re‑scan the string lead to unnecessary O(n²) time.
• A sliding window approach lets you maintain a current substring window that expands and contracts in O(1) time per character.
• Using a hash map (or an array for ASCII) to store the most recent index of each character enables instant checks for repeats.

Core Solution: Sliding Window Technique

How the Sliding Window Works

1. Initialize two pointers, left and right, both starting at 0.
2. Expand the window by moving right forward, adding the new character to a dictionary that records its latest index.
3. Detect a repeat when the character at right already exists within the current window (its index is ≥ left).
4. Shrink the window by moving left to one position after the last occurrence of the repeated character, thereby restoring the “no‑repeat” invariant.
5. Update the maximum length after each expansion.

Italic notation highlights the term sliding window, which is the heart of this algorithm.

Step‑by‑Step Algorithm

1. Set max_len = 0, left = 0.
2. Create an empty dictionary last_seen.
3. Iterate right from 0 to len(s)-1:
   • Let char = s[right].
   • If char is in last_seen and last_seen[char] >= left, set left = last_seen[char] + 1.
   • Update last_seen[char] = right.
   • Compute current_len = right - left + 1.
   • If current_len > max_len, set max_len = current_len.
4. Return max_len.

Complexity Analysis

• Time complexity: O(n) – each character is processed once.
• Space complexity: O(min(m, n)) where m is the size of the character set (e.g., 128 for ASCII) and n is the string length, due to the dictionary storing indices.

Implementation Details

Python Code Example

def length_of_longest_substring(s: str) -> int:
    last_seen = {}
    left = 0
    max_len = 0
    for right, char in enumerate(s):
        if char in last_seen and last_seen[char] >= left:
            left = last_seen[char] + 1
        last_seen[char] = right
        max_len = max(max_len, right - left + 1)
    return max_len

The function follows the algorithm exactly, using a dictionary for O(1) look‑ups.

Translating to Other Languages

• Java: Use an int[128] array for ASCII characters, initializing with -1.
• C++: A unordered_map<char, int> works similarly, with begin() and end() iterators for window bounds.
• JavaScript: A plain object {} serves as the hash map; remember to coerce the key to a string.

Common Mistakes and Edge Cases

Off‑by‑One Errors

A frequent bug occurs when left is set to last_seen[char] instead of last_seen[char] + 1. This leaves the repeated character inside the window, violating the no‑repeat rule.

Handling Unicode

The algorithm works for any Unicode string because the dictionary keys are characters, not byte values. Ensure your language’s string handling treats Unicode code points as single characters (e.g., Python 3 does this automatically).

Frequently Asked Questions

Q1: Can the algorithm be adapted to return the actual substring, not just its length?
Yes. Keep track of the start index of the best window (best_start) whenever max_len updates, then slice s[best_start:best_start+max_len] at the end.

Q2: What if the input string is empty?
The loop never runs, max_len stays 0, and the function correctly returns 0.

Q3: Does the solution work for very long strings (e.g., 10⁶ characters)?
Absolutely. The linear time complexity ensures it runs in a fraction of a second, and the dictionary size stays bounded by the character set Most people skip this — try not to. No workaround needed..

Conclusion

Mastering the longest substring without repeating characters leetcode problem equips you with a versatile sliding window pattern that appears in many other interview questions, such as finding longest substrings with certain properties, minimum window substrings, and more. By maintaining a dynamic window and a hash map of character indices, you achieve optimal O(n) time and O(1) auxiliary space, delivering a solution that is both efficient and easy to explain. Practicing this technique will sharpen your problem‑solving skills, boost your confidence in coding interviews, and ultimately help you write cleaner, faster code in any language.