Longest Substring Without Repeating Characters

Sliding Window

Problem

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

For example:

Input: String="aabccbb"
Output: 3
Explanation: The longest substring without 
any repeating characters is "abc".

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

Input: String="abbbb"
Output: 2
Explanation: The longest substring without 
any repeating characters is "ab".

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.

Input: s = ""
Output: 0

Thought Process

• Would we use a dictionary to keep track of distinct characters?

  • Yes, using a dictionary to map letters to their index's so we know where the repeating character previously was

• When would we slide the window forward?

  • Slide the window forward and update starting window when we come across a repeating letter.

• We can use a hash map to remember the last index of each character we have processed. Whenever we get a repeating character, we will shrink our sliding window to ensure that we always have distinct characters in the sliding window.

• When we come across a repeating character already in our dictionary, we need to check if current window start index is greater than the previous repeating character's index. If this is the case then we'll just keep starting index the same.

Solution

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        letterDict = {}
        maxLength = 0
        start = 0
        
        for i in range(len(s)):
            letter = s[i]
            
            if letter in letterDict:
                start = max(start,letterDict[letter]+1)
            
            letterDict[letter] = i
            maxLength = max(maxLength, i-start+1)
            
        return maxLength
        

Key Points

• Using a dictionary to keep track of letters we have come across and their index

• To ensure we have distinct characters in our window, when we come across a repeating character, we find that repeating character in our dictionary and update the starting window index to the index pass the repeating character, i.e. shrinking our sliding window.

• If we come across a repeating character, check if the index of the start window is greater than the repeating characters index+1 because we don't want to change the index of the sliding window if this is the case.

Time Complexity

• Time: $O(n)$

  • f

• Space: $O(K)$ where K is the number of distinct characters in the input string. This also means $K <= N$ , because in the worst case, the whole string might not have any repeating character, so the entire string will be added to the HashMap. Having said that, since we can expect a fixed set of characters in the input string (e.g., 26 for English letters), we can say that the algorithm runs in fixed space $O(1)$ ; in this case, we can use a fixed-size array instead of the HashMap.