Medium

Longest Substring Without Repeating Characters

056

Given a string s, return the length of its longest contiguous substring that contains no repeated characters.

EXAMPLES

Example 1

Input
{
  "s": "abcabcbb"
}

Output
3

FUNCTION SHAPE

s: string→int

SOLUTION NOTE

The function is monotonic: TTTFFFF. We check if the current character s[r] is already present in our window. If it is, increment the left pointer until we get rid of that previous instance.

Reveal reference solution +

pythonREFERENCE

def lengthOfLongestSubstring(self, s: str) -> int:
    n, l, res, freq = len(s), 0, 0, Counter()

    for r in range(n):
        freq[s[r]] += 1

        while freq[s[r]] >= 2:
            freq[s[l]] -= 1
            l += 1

        res = max(res, r - l + 1)

    return res

TimeO(n)

SpaceO(26) = O(1)

Open on LeetCode ↗