We are in Beta and we are offering 50% off! Use code BETATESTER at checkout.
You can access a significantly larger sample of the platform's content for free by logging in with your Gmail account. Sign in now to explore.

Longest substring without repeating characters (Leetcode 3)

Data Structures and Algorithms Medium Seen in real interview

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

Examples:

  • Input: abcabcbb
  • Output:3


  • Input: aaaaaaa
  • Output: 1
We can use a deque to keep track of the current substring without repeating characters. Every time we see a character that we have already seen, we remove all the elements from the queue up to and including the first occurrence of that character. However, before we remove those elements, we write down the size of the queue as it might be the maximum substring.

For the search operation, we use a hashset that takes constant search time. Everytime we remove elements from the queue, we also need to remove elements from the hashset (removal is also constant time).

from collections import deque

def lengthOfLongestSubstring(s: str) -> int:
    q = deque()
    seen = set()
    ans = 0
    for l in s:
        if l in seen:
            ans = max(ans, len(q))
            while q:
                tmp = q.popleft()
                seen.remove(tmp)
                if tmp == l:
                    break
        q.append(l)
        seen.add(l)
    return max(ans, len(q))


The time complexity of this solution is \(O(n)\) as we are not using any nested loop, and l in seen, popleft, and remove operations are \(O(1)\).

Here is an example:

inputs = "abcabcbb"
print(lengthOfLongestSubstring(inputs))
## 3
Topics

Hash, Sliding Window
Similar questions

Provide feedback