Given a string s, find the length of the longest substring without repeating 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.
Example 4:
Input: s = "" Output: 0
Constraints:
0 <= s.length <= 5 * 104s consists of English letters, digits, symbols and spaces.Source
def length_longest_substring(string):
"""Naive Sliding Windows approach with Hash Table of booleans
Time complexity: O(n)
Space complexity: O(n)
"""
used = {}
left = max_length = 0
for right, char in enumerate(string):
while char in used:
del used[string[left]]
left += 1
used[char] = True
max_length = max(max_length, right-left+1)
return max_length
def length_longest_substring(string):
"""Better Sliding Windows with Hash Table of index to avoid unecessary checks (i.e. the while loop)
Time complexity: O(n)
Space complexity: O(n)
"""
used = {}
left = max_length = 0
for right, char in enumerate(string):
if char in used and left <= used[char]: # check last time we saw char, if it was after left
left = used[char]+1 # and now start from index+1
used[char] = right # constantly update with most recent index
max_length = max(max_length, right-left+1)
return max_length
s = "abcabcbb"
length_longest_substring(s)
3
s = "bbbbb"
length_longest_substring(s)
1
s = "pwwkew"
length_longest_substring(s)
3
s = ""
length_longest_substring(s)
0