3. Longest Substring Without Repeating Characters
## description
## 3. Longest Substring Without Repeating Characters
Given a string s, find the length of the longest substring without duplicate characters.
Example 1:
1Input: s = "abcabcbb"
2Output: 3
3Explanation: The answer is "abc", with the length of 3. Note that "bca" and "cab" are also correct answers.Example 2:
1Input: s = "bbbbb"
2Output: 1
3Explanation: The answer is "b", with the length of 1.Example 3:
1Input: s = "pwwkew"
2Output: 3
3Explanation: The answer is "wke", with the length of 3.
4Notice that the answer must be a substring, "pwke" is a subsequence and not a substring.- –0 <= s.length <= 5 * 104
- –s consists of English letters, digits, symbols and spaces.
Constraints:
## notes
### Intuition
A sliding window maintains the current substring. When a duplicate character enters from the right, shrink from the left until the duplicate is removed, ensuring all characters in the window are unique.
### Implementation
Use a set to track characters in the current window. Iterate with the right pointer. If the character at r is already in the set, remove characters from the left (incrementing l) until the duplicate is gone. Add the current character to the set and update the maximum length (r - l + 1).
### Edge-cases
The window size calculation is r - l + 1 (inclusive on both ends). Empty strings return 0 naturally since the loop doesn't execute.
- –Time: O(n) — each character added and removed from set at most once
- –Space: O(min(n, m)) — where m is the character set size (26 for lowercase letters)
### Complexity
## solution
1from typing import List
2
3class Solution:
4 def lengthOfLongestSubstring(self, s: str) -> int:
5 max_length = 0
6 charSet = set()
7 l = 0
8 for r in range(len(s)):
9 while s[r] in charSet:
10 charSet.remove(s[l])
11 l += 1
12 charSet.add(s[r])
13 max_length = max(max_length, r - l + 1)
14
15 return max_length
16
17
18
19
20if __name__ == "__main__":
21 # Include one-off tests here or debugging logic that can be run by running this file
22 # e.g. print(solution.two_sum([1, 2, 3, 4], 3))
23 solution = Solution()
24