longest-substring-without-reapeating-characters

Longest Substring without Repeating Characters

• A solution that beats 98.90% in time and 98.03% in space
• https://leetcode.com/problems/longest-substring-without-repeating-characters

To save some lines, it is safe to just update the max_len at each iteration. This doesn’t change the asymptotic complexity.

Although this algorithm runs in $O(n)$ time, as the substring length is capped. It may look like a $O(n^2)$ solution though.

max_len = 0
substr = ""
for c in s:
    index = substr.rfind(c)
    if index == -1:
        substr += c
    else:
        substr = substr[index + 1:] + c
    max_len = max(len(substr), max_len)
return max_len