Longest Substring Without Repeating Characters

Problem

Given a string, find the length of the longest substring without repeating characters.

Example 1:

Input: "abcabcbb"  
Output: 3  
Explanation: The answer is "abc", with the length of 3.  

Example 2:

Input: "bbbbb"  
Output: 1  
Explanation: The answer is "b", with the length of 1.  

Example 3:

Input: "pwwkew"  
Output: 3  
Explanation: The answer is "wke", with the length of 3.  
             Note that the answer must be a substring, "pwke" is a subsequence and not a substring.

Input

• s - a string

Approach

The brute force approach is to have double for-loops and convert each sub-array into a set, recording the count of the set each time whenever we find a greater count.

The optimal solution is to make use of a window by using two pointers.
Have one pointer be the left side of the window and one pointer be the right side of the window.

As we traverse the string, if we encounter a character that we have not seen before, add that character to a set and extend the right side of the window to the right by 1.

If we encounter a character that we have seen before, then keep extending the left side of the window to the right until we reach the character that we have seen before. As we extend our left pointer to the right by 1, we should remove the character from the set when it falls out of our sub-window. When we eventually reach the character that we have seen before, keep that character in the set, but extend the left pointer to the right by 1 again, so that we will have a new non-repeating substring.

Solution

    def lengthOfLongestSubstring(self, s: 'str') -> 'int':
        if len(s) == 0:
            return 0

        i, j = 0, 1
        longest_count = 0

        seen = set(s[i])
        while i < j and j < len(s):
            if s[j] not in seen:
                seen.add(s[j])
            else:
                longest_count = max(len(seen), longest_count)

                # Narrow down elements of the subwindow from the left until we encounter the duplicate
                while i < j and j < len(s) and s[i] != s[j]:
                    seen.remove(s[i])
                    i += 1

                # We're at first instance of duplicate char, with the second instance being s[j],
                # so increment i again so that duplicates are no longer in the subwindow [i, j]
                i += 1
            j += 1

        longest_count = max(len(seen), longest_count)
        return longest_count