3.Longest_Substring_Without_Repeating_Characters_(Medium).md

3. Longest Substring Without Repeating Characters (Medium)

Date and Time: Jun 4, 2024, 12:10 PM (EST)

Link: https://leetcode.com/problems/longest-substring-without-repeating-characters/

Question:

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

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.

Edge Case 1:

Input: s = " "

Output: 1

Edge Case 2:

Input: s = "abba"

Output: 2

Walk-through:

Maintain a sliding window with non-repeated characters. When there is no repeated character exists, we repeatedly update res = max(res, r - l + 1). When we have a char that exists in hashmap{}, we start shrinking the sliding window by removing the left-most character.

My Solution:

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        # Maintain a sliding window and a hashmap for all the visited char
        # When a repeated word exits, we update res, shrink the window until the new char does not exist in hashmap

        # TC: O(n), n = len(s), SC: O(n)
        l, res = 0, 0
        hashmap = {}
        for r in range(len(s)):
            # Repeatedly update res, when there is no duplicate char exists
            if s[r] not in hashmap:
                res = max(res, r - l + 1)
            # Shrink the sliding window
            while s[r] in hashmap:
                del hashmap[s[l]]
                l += 1
            hashmap[s[r]] = 1
        return res

Time Complexity: $O(n)$, n is length of s.
Space Complexity: $O(n)$