Solution 1 HashMap
class Solution:
def lengthOfLongestSubstring(self, s: str) -> int:
charmap = {}
ans = 0
i, j = 0, 0
while i < len(s) and j < len(s):
if s[j] not in charmap or charmap[s[j]] < i:
charmap[s[j]] = j
ans = max(ans, j - i + 1)
j += 1
else:
i = charmap[s[j]] + 1
charmap[s[j]] = j
ans = max(ans, j - i + 1)
j += 1
return ans
Time complexity : O ( n ) . Index j will iterate n times. Space complexity O(min(m,n)). We need O(k) space for the sliding window, where k is the size of the Set. The size of the Set is upper bounded by the size of the string n and the size of the charset/alphabet m.
Solution 2 ASCII and Array
class Solution:
def lengthOfLongestSubstring(self, s: str) -> int:
ans = 0
i = 0
charmap = [0] * 256
for j in range(len(s)):
i = max(charmap[ord(s[j])], i)
ans = max(ans, j - i + 1)
charmap[ord(s[j])] = j + 1
return ans
Time O(n). Space O(1).
步步发财 