Longest Substring without Repeating Characters

The solution uses a sliding window and uses O(n) time and O(n) space.
There are many cases to take care of.

1. We can skip the process string less than size 2.
2. Iterate the string, checking each char as key in the hash, adding if not present.
If not present in hash, add each char as key and index as value.
3. If present in hash, check if the index is more than the window start.
Calculate the window size and update max.
4. Check the max again at the time of return.
``````class Solution(object):
def lengthOfLongestSubstring(self, s):
"""
:type s: str
:rtype: int
"""
if len(s) < 2:
return len(s)

wstart = wend = 0
charMap = {}
maxLen = 0
currentLen = 0

while wend < len(s):
if s[wend] in charMap and charMap[s[wend]] >= wstart: #abba
currentLen = wend - wstart
maxLen = max(maxLen, currentLen)
wstart = charMap[s[wend]] + 1

charMap[s[wend]] = wend
wend += 1

# The expression wend - wstart gets the case of last
# character used for len count.
return max(maxLen, wend - wstart)
``````

Reference

Written with StackEdit.

This site uses Akismet to reduce spam. Learn how your comment data is processed.