3. Longest Substring Without Repeating Characters
MediumLeetCodeGiven 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.
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 * 104
- s consists of English letters, digits, symbols and spaces.
How to solve the problem
- Approach: Sliding Window
Code
- Hash Map
Python
class Solution:
def lengthOfLongestSubstring(self, s: str) -> int:
left = 0
count = Counter() # hashmap k: char value: int
ans = 0
for right, x in enumerate(s):
count[x] += 1
while count[x] > 1:
count[s[left]] -= 1
left += 1
ans = max(ans, right - left + 1)
return ans
- Hash Set
Python
class Solution:
def lengthOfLongestSubstring(self, s: str) -> int:
left = 0
seen = set() # hash set, no need to record counter times. We only care this character is duplicated or not
ans = 0
for right, x in enumerate(s):
while x in seen:
seen.remove(s[left])
left += 1
seen.add(x)
ans = max(ans, right - left + 1)
return ans
Complexity
- Time complexity: O(n)
- Space complexity: O(1) The length of the longest string is 128(ASCII).
Comments
No comments yet. Be the first to comment!