0003-longest-substring-without-repeating-characters¶
Try it on leetcode
Description¶
Given a string s, find the length of the longest substring without duplicate characters.
Example 1:
Input: s = "abcabcbb" Output: 3 Explanation: The answer is "abc", with the length of 3. Note that"bca"and"cab"are also correct answers.
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.
Constraints:
0 <= s.length <= 5 * 104sconsists of English letters, digits, symbols and spaces.
Solution(Python)¶
class Solution:
def lengthOfLongestSubstring(self, s: str) -> int:
# abcabcbb
#
# i<j < n
# 0 -> n
# lookup ->
# j -? n
# invlaid shrink left end
# updare answer
# valid no duplicates
#
# abcad
# l = 0
# r = 0
# cur_length = 0
# max_legth = 0
#
# l = 0
# r=1
l = 0
lookup = set()
maxx_len = 0
for r in range(len(s)):
while lookup and s[r] in lookup:
lookup.remove(s[l])
l+=1
maxx_len = max(maxx_len, r -l + 1)
lookup.add(s[r])
return maxx_len