Longest substring without repeating characters (Leetcode 3)
Find if Path Exists in Graph (Leetcode 1971)
Minimum remove to make valid parentheses (Leetcode 1249)
Find if Path Exists in Graph (Leetcode 1971)
Minimum remove to make valid parentheses (Leetcode 1249)
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, andremoveoperations are \(O(1)\).
Here is an example:
## 3Hash, Sliding Window
- Find if Path Exists in Graph (Leetcode 1971) Medium (DFS, BFS)
- Remove duplicates in place (Leetcode 26) Easy (Array, Two pointers)
- K Closest Points to Origin (Leetcode 973) Easy (Heap)
- Number of recent calls (Leetcode 933) Easy (Queue, DEQueue)
- Sort an Array (Leetcode 912) Medium (Recursion, Sorting)
Thank you, we have received your feedback.