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.

Leave a Reply

Please log in using one of these methods to post your comment:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

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

%d bloggers like this: