3. Longest Substring Without Repeating Characters

Reformulated question¶

Find the maximum length of a contiguous substring of s that contains no repeated character.

Example:

s = "pwwkew" -> 3
("wke" is valid, "pwke" is not because it is not contiguous)

Key trick¶

Use a sliding window.

Keep a left boundary of the current valid substring.
For each character, if it was seen inside the current window, jump the left boundary right after its previous index.
Track the best window length.

Trap¶

Confusing substring with subsequence.
Moving the left pointer backward instead of only forward.
Resetting the whole window on a duplicate instead of shrinking just enough.
Forgetting to handle duplicates that were seen before but are no longer inside the current window.

Why this question is interesting¶

It turns a naive \(O(n^2)\) scan into an \(O(n)\) solution with one pass.

Good test of sliding window thinking.
Good test of handling indices carefully.

Solve the problem with idiomatic python¶

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        # last index where each character appeared
        last_seen = {}

        left = 0
        best = 0

        for right, ch in enumerate(s):
            # If ch is inside the current window, move left past it.
            if ch in last_seen and last_seen[ch] >= left:
                left = last_seen[ch] + 1

            last_seen[ch] = right
            best = max(best, right - left + 1)

        return best

Pytest test¶

import pytest

@pytest.mark.parametrize(
    ("s", "expected"),
    [
        ("", 0),
        (" ", 1),
        ("a", 1),
        ("bbbbb", 1),
        ("abcabcbb", 3),
        ("pwwkew", 3),
        ("dvdf", 3),
        ("abba", 2),
        ("tmmzuxt", 5),
        ("anviaj", 5),
    ],
)
def test_lengthOfLongestSubstring(s, expected):
    assert Solution().lengthOfLongestSubstring(s) == expected

Comment my solution¶

Your solution is correct on common cases, but it is more complicated than needed.

The nested for inside while makes the window logic harder to reason about.
Tracking both size and end - start is redundant.
The duplicate handling is clever, but index-based last-seen tracking is simpler and more standard for interviews.
Time complexity is still \(O(n)\), but the usual dictionary solution is shorter and easier to explain.

## Solution
class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        longest = 0
        start, end = 0, 0
        seen, size = set(), 0

        while end < len(s):
            for _ in range(end, len(s)):
                if s[end] in seen:
                    break
                seen.add(s[end])
                size += 1
                end += 1

            longest = max(longest, size)
            if not end < len(s):
                break
            # Skip value equal to s[end] but at a previous
            # index in the sliding window while still keeping
            # it in seen
            while s[start] != s[end]:
                seen.remove(s[start])
                start += 1
                size -= 1
            start += 1
            end += 1

        return longest

Solution().lengthOfLongestSubstring(" ") # 1
Solution().lengthOfLongestSubstring("a") # 1
Solution().lengthOfLongestSubstring("abcabcbb") # 3