Longest Substring Without Repeating Characters (LeetCode 3)
Given a string, find the length of the longest substring without repeating characters.
Example 1:
1 2 3
Input: "abcabcbb" Output: 3 Explanation: The answer is "abc", with the length of 3.
Example 2:
1 2 3
Input: "bbbbb" Output: 1 Explanation: The answer is "b", with the length of 1.
Example 3:
1 2 3 4
Input: "pwwkew" Output: 3 Explanation: The answer is "wke", with the length of 3. Note that the answer must be a substring, "pwke" is a subsequence and not a substring.
deflengthOfLongestSubstring(s: str) -> int: """ Return the length of the longest substring of a given string. Parameters ---------- s: str The given string, could be "" Returns ------- The length of the longest substring: int """ res = 0 slide = [] n = len(s) i,j = 0,0 while i < n: if s[i] notin slide: slide.append(s[i]) i += 1 res = max(res, len(slide)) else: while s[i] in slide: slide.remove(s[j]) j += 1 return res
# 优化1 res = 0 slide = set() n = len(s) i,j = 0,0 while i < n: if s[i] notin slide: slide.add(s[i]) i += 1 res = max(res, len(slide)) else: while s[i] in slide: slide.remove(s[j]) j += 1 # 优化2 res = 0 slide = set() n = len(s) i,j = 0, 0 while i < n and j < n: if s[i] notin slide: slide.add(s[i]) i += 1 res = max(res, len(slide)) # or i - j else: slide.remove(s[j]) j += 1 # 优化3 res = 0 slide = dict() n = len(s) i,j = 0,0 while i < n: if s[i] in slide: j = max(slide[s[i]], j) # because we do not delete those elements in slide slide[s[i]] = i+1# add one res = max(res, i+1-j) # add one for len(s) == 1 i += 1
优化 3 虽然理论上看起来很容易理解,但代码看起来貌似不是太直观。不过这种方法肯定是最有效率的,因为其他方法都需要 remove,如果是 set 还好复杂度为 O(1),如果是 list 复杂度为 O(N),那肯定是不能接受的。