Sliding window for longest distinct substring in Python

Extend the right end, shrink the left end past duplicates, and track the maximum window length; O(n) time.

File: sliding_window_longest_substring.py, 25 lines
Level: I0 not checked yet
Toolchain: Python 3.14, pytest 9
Test framework: pytest
Run the tests: python3 -m pytest

sliding_window_longest_substring.pyRaw GitHub

# SPDX-License-Identifier: MIT
# Part of https://algorithm.tamnd.com/sliding-window-longest-substring/. The authors are listed in prov/H69540.jsonl.

from collections.abc import Hashable, Sequence


def longest_distinct_substring(s: Sequence[Hashable]) -> tuple[int, int]:
    """Return (length, start) of the leftmost longest substring of s with no repeated item.

    Works for strings and for any sequence of hashable items.
    Cost: O(n) expected time with a dict for the last positions.
    """
    last: dict[Hashable, int] = {}  # @line L1
    left, best, start = 0, 0, 0
    for r, c in enumerate(s):  # @line L2
        left = max(left, last.get(c, -1) + 1)  # @line L3
        last[c] = r  # @line L4
        if r - left + 1 > best:  # @line L5
            best, start = r - left + 1, left
    return best, start  # @line L6


def length_of_longest_substring(s: str) -> int:
    """Return only the length, as in the usual statement of the problem."""
    return longest_distinct_substring(s)[0]

test_sliding_window_longest_substring.py 39 lines

# SPDX-License-Identifier: MIT
# Part of https://algorithm.tamnd.com/sliding-window-longest-substring/. The authors are listed in prov/H69540.jsonl.

import random

from sliding_window_longest_substring import length_of_longest_substring, longest_distinct_substring


def brute(s: str) -> tuple[int, int]:
    best = (0, 0)
    for i in range(len(s)):
        for j in range(i, len(s)):
            if len(set(s[i : j + 1])) == j - i + 1 and j - i + 1 > best[0]:
                best = (j - i + 1, i)
    return best


def test_example() -> None:
    assert longest_distinct_substring("abcabcbb") == (3, 0)
    assert longest_distinct_substring("bbbbb") == (1, 0)
    assert longest_distinct_substring("pwwkew") == (3, 2)


def test_edges() -> None:
    assert longest_distinct_substring("") == (0, 0)
    assert longest_distinct_substring(" ") == (1, 0)
    assert longest_distinct_substring("abba") == (2, 0)
    assert longest_distinct_substring("dvdf") == (3, 1)
    assert longest_distinct_substring("abcdef") == (6, 0)
    assert longest_distinct_substring([1, 2, 1, 3, 4]) == (4, 1)
    assert length_of_longest_substring("tmmzuxt") == 5


def test_against_brute_force() -> None:
    rng = random.Random(20261104)
    for _ in range(2000):
        n = rng.randrange(0, 16)
        s = "".join(rng.choice("abcde"[: rng.randrange(1, 6)]) for _ in range(n))
        assert longest_distinct_substring(s) == brute(s)

What the next level needs

the tests did not run in this build

Read the full page about Sliding window for longest distinct substring