← Back to DevBytes
Python August 06, 2026 9 min read

Solving Longest Substring Without Repeating in Python: Step-by-Step Guide

Introduction to the Longest Substring Without Repeating Characters Problem

The "Longest Substring Without Repeating Characters" is one of the most classic algorithmic problems you will encounter in coding interviews and competitive programming. Given a string, the task is to find the length of the longest contiguous substring that contains no duplicate characters. While the problem statement sounds simple, crafting an efficient solution requires a solid understanding of sliding window techniques and hash-based lookups.

In this tutorial, you will learn what the problem is, why it matters in real-world software engineering, how to implement multiple solutions in Python ranging from brute force to optimal, and the best practices to keep in mind when writing clean, performant code.

What Is the Longest Substring Without Repeating Characters?

Formally, the problem can be stated as follows: given a string s, return the length of the longest substring of s that contains no repeating characters. A substring is a contiguous sequence of characters within the string, as opposed to a subsequence, which can skip characters.

For example, given the input "abcabcbb", the longest substring without repeating characters is "abc", which has a length of 3. For the input "bbbbb", the answer is "b" with a length of 1. For "pwwkew", the answer is "wke" with a length of 3, not "pwke" because that is a subsequence, not a substring.

Key Observations

Why This Problem Matters

Beyond being a popular interview question at companies like Google, Amazon, and Microsoft, this problem teaches fundamental concepts that appear in many real-world scenarios. Understanding how to efficiently track unique elements within a moving window is a skill that transfers directly to problems involving data streams, network packet inspection, log analysis, and text processing.

For instance, imagine you are building a feature that detects the longest unique sequence of user actions in a session without repetition. Or consider a bioinformatics application where you need to find the longest unique nucleotide sequence in a DNA strand. The same sliding window logic applies.

From a learning perspective, this problem forces you to think about time and space complexity trade-offs. A naive solution might be easy to write but will fail on large inputs. The optimal solution requires careful pointer management and hash map usage, which are skills every developer should master.

Approach 1: Brute Force Solution

The most intuitive approach is to generate every possible substring and check whether each one contains all unique characters. While this works for small inputs, it has a time complexity of O(n^3) in the worst case, which is unacceptable for strings longer than a few hundred characters.

Implementation

def length_of_longest_substring_brute(s: str) -> int:
    n = len(s)
    max_length = 0

    for i in range(n):
        for j in range(i, n):
            substring = s[i:j + 1]
            if len(set(substring)) == len(substring):
                max_length = max(max_length, len(substring))

    return max_length

# Example usage
print(length_of_longest_substring_brute("abcabcbb"))  # Output: 3
print(length_of_longest_substring_brute("bbbbb"))     # Output: 1
print(length_of_longest_substring_brute("pwwkew"))    # Output: 3

This solution iterates over every starting index i and every ending index j, extracts the substring, and checks uniqueness by comparing the length of the substring with the length of its set representation. The set conversion itself is O(n), which is why the overall complexity is O(n^3).

Approach 2: Sliding Window with a Set

The sliding window technique dramatically improves efficiency. The idea is to maintain a window defined by two pointers, left and right, that expands to the right as long as no duplicate characters are encountered. When a duplicate is found, the left pointer moves forward until the duplicate is removed from the window.

We use a set to track the characters currently inside the window. This reduces the time complexity to O(2n) in the worst case, which simplifies to O(n), because each character is added and removed from the set at most once.

Implementation

def length_of_longest_substring_set(s: str) -> int:
    char_set = set()
    left = 0
    max_length = 0

    for right in range(len(s)):
        # If duplicate found, shrink window from the left
        while s[right] in char_set:
            char_set.remove(s[left])
            left += 1

        # Add current character and update max length
        char_set.add(s[right])
        max_length = max(max_length, right - left + 1)

    return max_length

# Example usage
print(length_of_longest_substring_set("abcabcbb"))  # Output: 3
print(length_of_longest_substring_set("dvdf"))      # Output: 3
print(length_of_longest_substring_set("anviaj"))    # Output: 5

Notice how the inner while loop shrinks the window incrementally. For the input "dvdf", when the second d is encountered at index 3, the left pointer moves from 0 to 2, removing d and v from the set, before adding the new d. The window then becomes "vdf" with length 3.

Approach 3: Optimized Sliding Window with a Dictionary

The set-based sliding window can be further optimized. Instead of moving the left pointer one step at a time when a duplicate is found, we can use a dictionary to store the most recent index of each character. When a duplicate is encountered, we can jump the left pointer directly past the previous occurrence of that character, skipping unnecessary iterations.

This approach achieves a true O(n) time complexity with a single pass through the string, and the space complexity is O(min(n, m)) where m is the size of the character set.

Implementation

def length_of_longest_substring_optimized(s: str) -> int:
    char_index = {}  # Maps character to its most recent index
    left = 0
    max_length = 0

    for right, char in enumerate(s):
        # If character is seen and its index is within the current window
        if char in char_index and char_index[char] >= left:
            left = char_index[char] + 1

        # Update the character's latest index
        char_index[char] = right

        # Update max length
        max_length = max(max_length, right - left + 1)

    return max_length

# Example usage
print(length_of_longest_substring_optimized("abcabcbb"))  # Output: 3
print(length_of_longest_substring_optimized("tmmzuxt"))    # Output: 5
print(length_of_longest_substring_optimized("abba"))       # Output: 2

The critical detail here is the condition char_index[char] >= left. This ensures we only jump the left pointer when the previous occurrence of the character is actually within the current window. Consider the input "abba": when we reach the second b at index 3, the previous b was at index 1, but left has already moved to 2 because of the earlier a duplicate. Without this check, we would incorrectly move left backwards.

Returning the Substring Itself

While the standard problem asks only for the length, a common follow-up in interviews is to return the actual substring. This requires tracking not just the maximum length but also the starting index of the best window found so far.

Implementation

def longest_substring_unique(s: str) -> str:
    char_index = {}
    left = 0
    max_length = 0
    start_index = 0

    for right, char in enumerate(s):
        if char in char_index and char_index[char] >= left:
            left = char_index[char] + 1

        char_index[char] = right

        current_length = right - left + 1
        if current_length > max_length:
            max_length = current_length
            start_index = left

    return s[start_index:start_index + max_length]

# Example usage
print(longest_substring_unique("abcabcbb"))  # Output: "abc"
print(longest_substring_unique("pwwkew"))    # Output: "wke"
print(longest_substring_unique(" "))         # Output: " "

By recording start_index whenever we find a longer window, we can slice the original string at the end to retrieve the answer. If there are multiple substrings of the same maximum length, this implementation returns the first one encountered.

Handling Edge Cases

A robust solution must handle edge cases gracefully. Here are the scenarios you should test:

Test Suite

def test_longest_substring():
    test_cases = [
        ("", 0),
        ("a", 1),
        ("aaaaa", 1),
        ("abcdef", 6),
        ("abcabcbb", 3),
        ("bbbbb", 1),
        ("pwwkew", 3),
        ("dvdf", 3),
        ("anviaj", 5),
        ("tmmzuxt", 5),
        ("abba", 2),
        ("a b c", 3),
        ("héllo", 4),
    ]

    for s, expected in test_cases:
        result = length_of_longest_substring_optimized(s)
        status = "PASS" if result == expected else "FAIL"
        print(f"{status}: input='{s}', expected={expected}, got={result}")

test_longest_substring()

Running this test suite validates that your implementation handles all the tricky cases correctly. The "abba" case is particularly important because it catches the common bug of not checking whether the previous character index is within the current window.

Best Practices

When implementing this solution in a professional setting, keep the following best practices in mind:

Production-Ready Implementation with Docstring

def length_of_longest_substring(s: str) -> int:
    """
    Find the length of the longest substring without repeating characters.

    Uses an optimized sliding window approach with a dictionary to track
    the most recent index of each character.

    Args:
        s: The input string to analyze.

    Returns:
        The length of the longest substring without repeating characters.

    Time Complexity: O(n) - single pass through the string
    Space Complexity: O(min(n, m)) - where m is the character set size
    """
    char_index: dict[str, int] = {}
    left = 0
    max_length = 0

    for right, char in enumerate(s):
        if char in char_index and char_index[char] >= left:
            left = char_index[char] + 1
        char_index[char] = right
        max_length = max(max_length, right - left + 1)

    return max_length

Performance Comparison

To understand why the optimized solution is worth the extra complexity, consider the performance differences across the three approaches on a large input string of 100,000 characters:

The dictionary approach is approximately twice as fast as the set approach on large inputs because it avoids the incremental shrinking of the window. For small inputs, the difference is negligible, but in performance-critical applications processing large streams of data, the optimization is meaningful.

Conclusion

The Longest Substring Without Repeating Characters problem is a cornerstone algorithm that every Python developer should understand thoroughly. Starting from the brute force approach and progressing to the optimized sliding window with a dictionary, you have seen how thoughtful use of data structures and pointer management can reduce time complexity from O(n^3) to O(n). The key insight is that maintaining a window of unique characters and jumping the left pointer past duplicates using a hash map eliminates redundant work. By following the best practices outlined in this tutorial, writing comprehensive tests for edge cases, and understanding the trade-offs between different approaches, you will be well-equipped to solve not only this problem but also the entire family of sliding window challenges that appear frequently in real-world software development and technical interviews.

— Ad —

Google AdSense will appear here after approval

← Back to all articles