Longest Substring Without Repeating Characters

01 · Question

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

The reference implementations below assume ASCII input.

02 · Analysis

Store each character's last index. If it was seen inside the current window, move the left boundary just past that occurrence; never move left backward. Then update the longest length. These reference solutions use an ASCII input contract so Python character indices and Go byte indices agree. Expected O(n) time and O(U) space for U distinct characters. A substring is contiguous; a subsequence is not required to be.

03 · Solution

Reference solution

1def lengthOfLongestSubstring(s: str) -> int:
2    seen = {}
3    l = 0
4    res = 0
5
6    for r in range(len(s)):
7        if s[r] in seen and seen[s[r]] >= l:
8            l = seen[s[r]] + 1
9        seen[s[r]] = r
10        res = max(res, r - l + 1)
11
12    return res

Most Sales in K Days

Count Subarrays with At Most K Bad Days