3. Longest Substring Without Repeating Characters

MediumLeetCode

Given a string s, find the length of the longest substring without duplicate 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. 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.

How to solve the problem

• Approach: Sliding Window

Code

• Hash Map

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        left = 0
        count = Counter()  # hashmap k: char value: int
        ans = 0
        for right, x in enumerate(s):
            count[x] += 1
            while count[x] > 1:
                count[s[left]] -= 1
                left += 1
            ans = max(ans, right - left + 1)
        return ans

• Hash Set

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        left = 0
        seen = set() # hash set, no need to record counter times. We only care this character is duplicated or not
        ans = 0
        for right, x in enumerate(s):
            while x in seen:
                seen.remove(s[left])
                left += 1
            seen.add(x)
            ans = max(ans, right - left + 1)
        return ans

Complexity

• Time complexity: O(n)
• Space complexity: O(1) The length of the longest string is 128(ASCII).