↔️3. Longest Substring Without Repeating Characters

Medium | Grind 75 | Spetember 15th Friday, 2022

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

Constraints:

• 0 <= s.length <= 5 * 10^4

• s consists of English letters, digits, symbols and spaces.

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.

SOLUTION

In order to find the longest non-repeating substring, we will use the sliding window technique. This technique involves keeping track of the characters we have seen so far using a dictionary, and updating the start value of the substring accordingly. Every time we encounter a repeating character, we check to see if the start value of the substring is lower than the index of the previous instance of that character. If it is, we update the start value to be the previous instance's index + 1. This ensures that our substring does not contain any repeating characters. We then calculate the maximum length by subtracting the end value (which increments with every iteration) from the start value.

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        # start index of non-repeating substring
        start = 0 
        # end index of non-repeating substring
        end = 0 
        # dict to track seen letters
        freq_dict = Counter()
        # maximum lenght of non-repeating substring
        max_length = 0
        
        
        for char in s:
            end += 1
            
            # if the current letter has been seen before
            if char in freq_dict: 
                # only update start if start is less than the index of the previously seen letter
                start = max(freq_dict[char], start)
                # update the index of the last seen letter
                freq_dict[char] = end
            
            else:
                # add the letter in the dict and continue iterating
                freq_dict[char] = end
            
            # calculate the length of the substring
            max_length = max(max_length, end-start)
        
        return max_length
                
        

TIME AND SPACE COMLPEXITY

TIME: O(n) where n is the length of the string. We iterate over the string once.

SPACE: O(n) In the worst case where there are no repeating characters, our dictionary needs space n to store all the characters.