Problem Statement

Description

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

Examples

Example 1:

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

Example 2:

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

Example 3:

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

Constraints

  • 0 <= s.length <= 5 * 104
  • s consists of English letters, digits, symbols and spaces.

Key Insights

  • To solve this problem in O(N) time, we can design a Sliding Window algorithm that uses a Hash Map data structure. The Sliding Window will use left l and right r pointers to define the window and a Hash Map mp to keep track of the indexes of each unique character in the window. (Note: mp contains the indexes of all previously seen characters–even if they don’t appear in the window. There’s no need to purge these.)

  • For each iteration of r, check if the current character ch appears in mp. If it does, further check if the left l pointer is at or before the index of ch i.e l <= mp[ch].

    • If True: Resize the window to exclude the repeated character, i.e. l = mp[ch] + 1.
    • Otherwise: Update the length of the longest unique substring ans = max(ans, r - l + 1

  • Finally, update the “index of the last occurrence of ch”, i.e. mp[ch] = r. Since this statement is the last thing that happens in the loop, it becomes historical information for the next iteration.

Python Solution

Optimized Sliding Window


class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        """
        0   1   2   3   4   5   6   7
        a   b   c   a   b   c   b   b
                        ^r
            ^l

        Time:   O(n)
        Space:  O(min(n, m)) | m=size of charset
        """
        l = 0
        n = len(s)
        ans = 0
        mp = {}

        # Right pointer (r) slides across whole range
        for r in range(n):

            # We will use the current character (ch) multiple times
            ch = s[r]
            
            # Resize window to exclude previous occurrence of (ch)
            if ch in mp and l <= mp[ch]:
                l = mp[ch] + 1
            
            # Update window size (ans) if (ch) appears once in the window
            else:
                ans = max(ans, r - l + 1)
            
            # Add "previous occurrence" of (ch) to hashmap (mp)
            mp[ch] = r

        # Return answer
        return ans