Longest substring without repeating characters

Longest Substring without Repeating Characters

As an experienced developer and educator in algorithms and data structures, I often guide professionals and technical founders through mastering real-world coding problems.

One such foundational problem is finding the longest substring without repeating characters, a frequent topic in coding interviews and systems requiring efficient string manipulation.

This article breaks down the problem using intuitive examples, explores different solution approaches from brute force to optimal, and demonstrates how to achieve O(n) time complexity. Whether you're practicing for interviews or optimizing production code, this guide is designed for clarity and performance.

Brute-Force Solution (Incorrect Logic Example)

def longest_substring_without_repeating_characters(s: str) -> int:
    """
    Attempted solution with incorrect logic: breaks on first repeat, doesn't track window.
    """
    char_map = set()
    max_length = 0

    for char in s:
        if char not in char_map:
            char_map.add(char)
        else:
            max_length = max(max_length, len(char_map))
            char_map.clear()  # Resets instead of sliding
    return max_length

Why It Fails:

    • It clears the entire set on any repeat instead of sliding the window.
    • Returns incorrect results for strings like "abcabcbb".
    • Time Complexity: O(n) but incorrect logic.

Brute-Force Solution (Correct Logic Example)

This version is now correct and implements the idea but is inefficient for long strings.
 

# Brute-force approach: Generate all substrings and check for uniqueness

def longest_substring_brute_force(s: str) -> int:
    max_len = 0
    for i in range(len(s)):
        seen = set()
        for j in range(i, len(s)):
            if s[j] in seen:
                break
            seen.add(s[j])
            max_len = max(max_len, j - i + 1)
    return max_len

Time Complexity
    • O(n²) because we are checking each substring.
Space Complexity
    • O(n) for the hash set used for checking duplicates.

Attempted Sliding Window (Incomplete Handling)

def longest_substring_without_repeating_characters(s: str) -> int:
    """
    Correct approach using sliding window, but logic needs tuning.
    """
    char_map = set()
    max_length = 0
    i, j = 0, 0

    while i < len(s) and j < len(s):
        if s[j] not in char_map:
            char_map.add(s[j])
            j += 1
        else:
            max_length = max(max_length, len(char_map))
            char_map.remove(s[i])
            i += 1
    return max_length

What's Missing:

    • Doesn’t update max_length after final loop ends.
    • Fix: Ensure max is checked after loop.

Here’s the optimal corrected version, using two pointers to dynamically adjust the window and ensure that every character in the window is unique.

# Correct sliding window solution using two pointers

def longest_substring_without_repeating_characters1(s: str) -> int:
    """
    Find the length of the longest substring without repeating characters.
    """
    char_map = set()
    max_length = 0

    i, j = 0, 0
    while i < len(s) and j < len(s):
        if s[j] not in char_map:
            char_map.add(s[j])
            j += 1
            max_length = max(max_length, j - i)
        else:
            char_map.remove(s[i])
            i += 1
    return max_length

Time Complexity

    • O(n), where n is the length of the string.

Space Complexity

    • O(n), for the hash set storing current substring characters.

Optimal Sliding Window Solution

def longest_substring_without_repeating_characters(s: str) -> int:
    """
    Optimal O(n) time complexity using sliding window with set.
    """
    seen = set()
    left = 0
    max_length = 0
    for right in range(len(s)):
        while s[right] in seen:
            seen.remove(s[left])
            left += 1
        seen.add(s[right])
        max_length = max(max_length, right - left + 1)

    return max_length

Why It Works

    • The left pointer only moves forward, ensuring each character is visited once.
    • At every step, the window [left, right] holds unique characters.
    • Time Complexity: O(n)
    • Space Complexity: O(min(n, a)) where a is the charset (e.g., 128 for ASCII)

Example Test Cases:

print("Expected : 3, Actual:", longest_substring_without_repeating_characters("abcabcbb"))
print("Expected : 0, Actual:", longest_substring_without_repeating_characters(""))
print("Expected : 1, Actual:", longest_substring_without_repeating_characters("bbbbb"))
print("Expected : 5, Actual:", longest_substring_without_repeating_characters("abcde"*20000))
print("Expected : 2, Actual:", longest_substring_without_repeating_characters("a"*50000 + "b"*50000))

Want to Write Faster, Cleaner Code Like This?

Knowing how to optimize problems like finding the longest substring without repeating characters is not just about cracking coding interviews—it’s about building faster, more efficient software.

If this guide helped you, your next step is to build consistency. Practice sliding window problems regularly. They're a game changer for both interviews and high-performance software engineering.

Ready to go pro with patterns like this? Study sliding window, two pointers, and hashing techniques—then put them to work. Stay sharp, stay fast.