# A Python solution - 85ms - O(n)

• ``````class Solution:
# @return an integer
def lengthOfLongestSubstring(self, s):
start = maxLength = 0
usedChar = {}

for i in range(len(s)):
if s[i] in usedChar and start <= usedChar[s[i]]:
start = usedChar[s[i]] + 1
else:
maxLength = max(maxLength, i - start + 1)

usedChar[s[i]] = i

return maxLength``````

• This post is deleted!

• Brilliant! Seems theres no way to improve it even a little bit. Thanks for sharing

• Graceful indeed,but it stiill can be optimised by check wether the remaining string length [start ~ ] are shorter then current max length. if it's, return.

• Thumbs up. Thank you

• Similar as what I did. I think it might be more compact to add
maxLen = max(maxLen, i-start+1)
outside the for loop. Thanks.

• if you use " if s[i] in usedChar ", this algorithm won't be O(n), it will be O(n^2)
tell me if i'm wrong

• `usedChar` is a hashtable, the lookup time is O(1) :)

• thx~. actually, i only know that usedchar[key] is O(1) before your comment.
now, i think you are right.

• "Graceful indeed,but it stiill can be optimised by check wether the remaining string length [start ~ ] are shorter then current max length. if it's, return."

I thought so too at the beginning. But turns out the maxLength can still grow if the remaining string contains chars that are not in the current maxLength string. So return at this point will result in smaller values than the truth.

• This is what I tried to do first. But failed in doing.
Then I came up with another solution.
Impressive, Thanks!

• but why i submit your code and get 300+ms???

• If you use 'enumerate', code will be more readable.

def lengthOfLongestSubstring(self, s):

``````    used = {}
max_length = start = 0
for i, c in enumerate(s):
if c in used and start <= used[c]:
start = used[c] + 1
else:
max_length = max(max_length, i - start + 1)

used[c] = i

return max_length``````

Clear, smart, great solution!
Thumbs up!

• @Google @motal Thanks a lot!

• Great solution, thanks a lot!

• This solution gave me goosebumps when I finally understood how it worked. Thanks, Thumbs Up

• This post is deleted!

• How about accessing the index of duplicate letter when necessary?

``````    max_length = 0
longest_substring = ''

for letter in s:
if letter not in longest_substring:
longest_substring += letter
else:
longest_substring = longest_substring[longest_substring.index(letter)+1:] + letter
# access the index of duplicate letter in the substring and leave the right side and plus the new letter

if len(longest_substring) > max_length:
max_length = len(longest_substring)

return max_length``````

• This post is deleted!

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