Longest Substring No Repeat

Problem

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

Approach

Sliding window with a dict tracking the last-seen index of each character. When a duplicate is found within the current window, jump the left pointer past the previous occurrence.

When to Use

Longest valid window — "longest substring/subarray without repeats", "maximum window satisfying constraint". Expand right, contract left only when the window becomes invalid. Streaming uniqueness checks.

Complexity

Time	O(n) -- single pass through the string
Space	O(min(n, alphabet_size)) for the last-seen dict

Implementation

SolutionTestsChallenge

longest_substring_no_repeat

Longest substring without repeating characters.

Problem

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

Approach

Sliding window with a dict tracking the last-seen index of each character. When a duplicate is found within the current window, jump the left pointer past the previous occurrence.

When to use

Longest valid window — "longest substring/subarray without repeats", "maximum window satisfying constraint". Expand right, contract left only when the window becomes invalid. Streaming uniqueness checks.

Complexity

Time: O(n) -- single pass through the string Space: O(min(n, alphabet_size)) for the last-seen dict

length_of_longest_substring

length_of_longest_substring(s: str) -> int

Return the length of the longest substring with no repeating chars.

length_of_longest_substring("abcabcbb") 3 length_of_longest_substring("bbbbb") 1 length_of_longest_substring("") 0

Source code in src/algo/sliding_window/longest_substring_no_repeat.py

def length_of_longest_substring(s: str) -> int:
    """Return the length of the longest substring with no repeating chars.

    >>> length_of_longest_substring("abcabcbb")
    3
    >>> length_of_longest_substring("bbbbb")
    1
    >>> length_of_longest_substring("")
    0
    """
    seen: dict[str, int] = {}
    left = best = 0

    for right, ch in enumerate(s):
        if ch in seen and seen[ch] >= left:
            left = seen[ch] + 1
        seen[ch] = right
        best = max(best, right - left + 1)

    return best

tests/sliding_window/test_longest_substring_no_repeat.py

"""Tests for longest substring without repeating characters."""

from hypothesis import given
from hypothesis import strategies as st

from algo.sliding_window.longest_substring_no_repeat import (
    length_of_longest_substring,
)


class TestLongestSubstringNoRepeat:
    def test_basic(self) -> None:
        assert length_of_longest_substring("abcabcbb") == 3

    def test_all_same(self) -> None:
        assert length_of_longest_substring("bbbbb") == 1

    def test_mixed(self) -> None:
        assert length_of_longest_substring("pwwkew") == 3

    def test_empty_string(self) -> None:
        assert length_of_longest_substring("") == 0

    def test_single_char(self) -> None:
        assert length_of_longest_substring("z") == 1

    def test_all_unique(self) -> None:
        assert length_of_longest_substring("abcdef") == 6

    @given(
        s=st.text(
            alphabet=st.sampled_from("abcde"),
            min_size=1,
            max_size=50,
        ),
    )
    def test_result_bounded_by_unique_chars(self, s: str) -> None:
        """Result cannot exceed the number of unique characters in s."""
        result = length_of_longest_substring(s)
        assert 1 <= result <= len(set(s))

    @given(
        s=st.text(
            alphabet=st.sampled_from("abcde"),
            min_size=1,
            max_size=50,
        ),
    )
    def test_matches_brute_force(self, s: str) -> None:
        """Cross-check against O(n^2) brute force."""
        expected = 0
        for i in range(len(s)):
            seen: set[str] = set()
            for j in range(i, len(s)):
                if s[j] in seen:
                    break
                seen.add(s[j])
            expected = max(expected, len(seen))
        assert length_of_longest_substring(s) == expected

Implement it yourself

Run: just challenge sliding_window longest_substring_no_repeat

Then implement the functions to make all tests pass. Use just study sliding_window for watch mode.

Reveal Solution

longest_substring_no_repeat

Longest substring without repeating characters.

Problem

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

Approach

Sliding window with a dict tracking the last-seen index of each character. When a duplicate is found within the current window, jump the left pointer past the previous occurrence.

When to use

Longest valid window — "longest substring/subarray without repeats", "maximum window satisfying constraint". Expand right, contract left only when the window becomes invalid. Streaming uniqueness checks.

Complexity

Time: O(n) -- single pass through the string Space: O(min(n, alphabet_size)) for the last-seen dict

length_of_longest_substring

length_of_longest_substring(s: str) -> int

Return the length of the longest substring with no repeating chars.

length_of_longest_substring("abcabcbb") 3 length_of_longest_substring("bbbbb") 1 length_of_longest_substring("") 0

Source code in src/algo/sliding_window/longest_substring_no_repeat.py

def length_of_longest_substring(s: str) -> int:
    """Return the length of the longest substring with no repeating chars.

    >>> length_of_longest_substring("abcabcbb")
    3
    >>> length_of_longest_substring("bbbbb")
    1
    >>> length_of_longest_substring("")
    0
    """
    seen: dict[str, int] = {}
    left = best = 0

    for right, ch in enumerate(s):
        if ch in seen and seen[ch] >= left:
            left = seen[ch] + 1
        seen[ch] = right
        best = max(best, right - left + 1)

    return best