LC 3 - Longest Substring Without Repeating Characters
Question
Given a string s, find the length of the longest substring without duplicate characters.
Example 1:
1
2
Input: s = "abcabcbb"
Output: 3
Explanation: The answer is “abc”, with the length of 3.
Example 2:
1
2
Input: s = "bbbbb"
Output: 1
Explanation: The answer is “b”, with the length of 1.
Example 3:
1
2
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 * 104sconsists of English letters, digits, symbols and spaces.
Links
Question here and solution here
Solution
concept
Use a sliding window and maintain a set of char seen so far. Whenever the r pointer seen a duplicate, we will move the l pointer until this duplicate is removed from the seen set.
Then we will move the r pointer again. We will then return the maximum length through a greedy method.
code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
class MySolution:
"""
sliding window
using 2 while loop
"""
def lengthOfLongestSubstring(self, s: str) -> int:
if not s:
return 0
l, r = 0, 0
ans = 0
char_set = set()
while r < len(s):
if s[r] not in char_set:
char_set.add(s[r])
ans = max(ans, r - l + 1)
r += 1
else:
while s[r] in char_set:
char_set.remove(s[l])
l += 1
return ans
class NeetSolution:
"""
sliding window
using for + while
"""
def lengthOfLongestSubstring(self, s: str) -> int:
charSet = set()
l = 0
res = 0
for r in range(len(s)):
while s[r] in charSet:
charSet.remove(s[l])
l += 1
charSet.add(s[r])
res = max(res, r - l + 1)
return res
Complexity
time: $O(n)$, n is the length of the string
space: $O(m)$, m is the total number of unique char in the string.