# A O(n) python solution with explain

• ``````class Solution(object):
def lengthOfLongestSubstring(self, s):
"""
:type s: str
:rtype: int
"""
index = {}  # cache the position of each char in current sub str
start = 0   # cache the position of the start char in current sub str
longest, current = 0, 0 # result, and the length of current sub str
for i, c in enumerate(s):
if c in index and index[c] >= start:
# current c is in current sub str
# we shuink the current str
current = current + start - index[c]
# then update the start position and the index of c
start = index[c]+1
index[c] = i
else:
# current c is not in current sub str
# we update the current str, and see if it's longer than
# the longest sub str
index[c] = i
current += 1
longest = max(longest, current)
return longest
``````

I think it should be O(n), it's not so fast as I thought though.
Pls let me know if anywhere it can be improved, thank you.

• great solution and detailed explanation, thank you!

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.