Skip to content

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
Python
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
Python
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).

Comments

No comments yet. Be the first to comment!